1550E - Stringforces - CodeForces Solution

#include<bits/stdc++.h>
#define N 200005
#define LL long long
#define DB double
#define eps 1e-7
#define inf 214748364
#define s_id set<node>::iterator
using namespace std;
int n,m,nxt[N],g[N<<1],f[N][20];char s[N];const int p=998244353;
inline int gcd(int x,int y){return !y?x:gcd(y,x%y);}
inline int power(int x,int y,int z){int res=1;while(y){if(y&1) res=1ll*res*x%z;y>>=1,x=1ll*x*x%z;} return res;}
inline void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
inline int read(){int res=0,f=1;char ch=getchar();while(!isdigit(ch)) (ch=='-')&&(f=-f,0),ch=getchar();while(isdigit(ch)) res=res*10+ch-'0',ch=getchar();return res*f;}
inline bool check(int x){
    // cout<<x<<'\n';
    for(int j=0;j<m;j++){
        nxt[n+1]=n+1;f[n+1][j]=inf;for(int i=n;i;i--){
            if(s[i]=='?'||s[i]-'a'==j) nxt[i]=nxt[i+1];else nxt[i]=i;
            if(nxt[i]-i>=x) f[i][j]=i+x;else f[i][j]=f[i+1][j];
        }
    }
    g[0]=1;for(int i=1;i<(1<<m);i++){g[i]=inf;for(int j=0;j<m;j++) if(i&(1<<j)) if(g[i^(1<<j)]!=inf) g[i]=min(g[i],f[g[i^(1<<j)]][j]);}return g[(1<<m)-1]!=inf;
}
inline void solve(int tc){
    cin>>n>>m;scanf("%s",s+1);int l=1,r=n/m;while(l<=r){int mid=(l+r)>>1;if(check(mid)) l=mid+1;else r=mid-1;} cout<<r<<'\n';
}
int main(){
    // freopen("data.in","r",stdin);
    int tc=1;
    // srand(time(NULL));
    // tc=read();
    while(tc--) solve(tc);
    return 0;
}