HARSTR: Editorial
Problem-code: HARSTR
Contest-Code: CSMH2021
Author: JAMI YASHWANTH
Editorialist: JAMI YASHWANTH
DIFFICULTY:
MEDIUM
PREREQUISITES:
binary search,bitmasks,brute force,dp,strings,two pointers
PROBLEM:
Harshdeep and Navdeep are best friends . Navdeep is good at String manipulation concept. Harshdeep challenged Navdeep to solve one problem related to strings .
Harshdeep gives a string s of length n. Each character is either one of the first k lowercase latin letters or a question mark. Navdeep’s task is to replace every question mark with one of the first k lowercase latin letters in such a way that the following value is maximized.
Let fi be the maximum length substring of string s, which consists entirely of the i-th Latin letter. A substring of a string is a contiguous subsequence of that string. If the i-th letter doesn’t appear in a string, then fi is equal to 0.
The value of a string s is the minimum value among fi for all i from 1 to k. Navdeep is good at string manipulation , but he is not able to solve this problem .
Navdeep asks you to help him.
Your task is to print maximum value the string can have?
SOLUTION:
#include <bits/stdc++.h>
using namespace std;
int read() {
int f = 1, x = 0; char c = getchar();
while(!isdigit(c)) {if(c == ‘-’) f = -f; c = getchar();}
while(isdigit(c)) {x = (x << 1) + (x << 3) + c - ‘0’; c = getchar();}
return x * f;
}
const int N = 2e5 + 5;
const int M = 20;
const int S = (1 << M);
int n, m;
char ch[N];
int p[N][M], lst[M], f[S];
void clear() {
for(int i = 0; i < S; i ++) f[i] = n + 1;
for(int i = 0; i < m; i ++) lst[i] = n;
for(int i = 0; i <= n; i ++)
for(int j = 0; j < m; j ++)
p[i][j] = n + 1;
}
bool chk(int mid) {
clear();
// cout << mid << " ::\n";
for(int i = n - 1; i >= 0; i --) {
if(ch[i] != ‘?’) lst[ch[i] - ‘a’] = i;
int cur = n;
// for(int j = 0; j < m; j ++)
// cur = min(cur, lst[j])
for(int j = 0; j < m; j ++) {
if(i + mid > cur)
p[i][j] = p[i + 1][j];
else
p[i][j] = i + mid;
cur = min(cur, lst[j]);
}
cur = n;
for(int j = m - 1; ~j; j --) {
if(i + mid > cur)
p[i][j] = p[i + 1][j];
cur = min(cur, lst[j]);
}
// cout << i << " " << cur << " <>\n";
// for(int j = 0; j < m; j ++) {
// cout << p[i][j] << " “;
// } cout << “\n”;
}
f[0] = 0;
for(int i = 0; i < (1 << m); i ++) {
if(f[i] >= n + 1) continue;
for(int j = 0; j < m; j ++) {
if(!(i & (1 << j))) {
f[i | (1 << j)] = min(f[i | (1 << j)], p[f[i]][j]);
}
}
}
return f[(1 << m) - 1] <= n;
}
int main() {
n = read(), m = read();
scanf(”%s", ch);
int l = 1, r = n, ans = 0;
while(l <= r) {
int mid = l + r >> 1;
if(chk(mid)) {
ans = mid; l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << “\n”;
return 0;
}