题目大意：

给定一个字符串s，长度为n，由字符'a'~'a'+k-1 和 '?' 组成，定义\(f_i\)为字符'a'+i 在s中的最长连续长度(连续的子串，且子串每一个字符均为'a'+i)，'?'可以替换为任意一个字母；求在所以替换方案中 \(Min_{i=0}^{k-1}~f_i\) 的最大值；

题目链接：

[]: https://codeforces.com/contest/1550/problem/E "传送门"

题目思路：

显然答案具有单调性，因此可以二分答案。考虑如何检验答案？可以枚举字符的排列作为'?'的替换方案，例如\(k=3\)，检验答案为2的情况，可以把？？？？？？换成\(aabbcc\)，即使按照排列顺序，依次对？做替换，直到当前字符最长连续长度满足答案，再考虑替换下一个字符，但是排列会出现大量的重复计算，所以我们可以用状压DP来优化排列的枚举。

设需要检验的答案为x，定义状态 \(f(i)\)表示满足所有字符\(j ~(~1<<j~\&~i~==1)\)的最长连续长度不少于x的最小右端点，

转移方程：\(f(i|1<<j)~=~Min(~f(i|1<<j)~,~R(j~,~f(i)+1)~), k满足 1<<j~ \& ~i==0\)，

\(R(i,j)\)表示以\(j\)起点，能够得到字符\(i\)最长连续长度不少于\(x\)的最小右端点，\(R(i,j)\)可以通过后缀最小值作预处理,

当 \(f(~(1<<k)-1~)>n\) 则说明不能在找到一种替换方案，使得所有字符最长连续长度的最小值不小于\(x\)；

AC代码：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef pair<double,double> pdd;
const int N=2e5+5;
const int M=18;
const int inf=0x3f3f3f3f;
const LL mod=1e9+7;
const double eps=1e-8;
const long double pi=acos(-1.0L);
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
LL read()
{
    LL x=0,t=1;
    char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') t=-1;
    while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
    return x*t;
}
int n,k;
char s[N];
int f[1<<M],r[M][N];
int check(int x)
{
    for(int i=0;i<k;i++)
    {
        r[i][n+1]=r[i][n+2]=n+1;//初始化n+1,n+2 的最右端点 >n
        int len=0;
        for(int j=n;j;j--)
        {
            if(s[j]=='?'||s[j]=='a'+i) len++;
            else len=0;
            r[i][j]=len>=x?j+x-1:r[i][j+1];
        }
    }
    f[0]=0;
    for(int i=1;i<(1<<k);i++) f[i]=n+1;//给f(i) 初始置为 >n ;
    for(int i=0;i<(1<<k);i++)
    {
        for(int j=0;j<k;j++)
        {
            if(1<<j&i) continue;
            f[1<<j|i]=min(f[1<<j|i],r[j][f[i]+1]);//f[i]最坏为n+1,f[i]+1=n+2,因此也要初始化n+2;
        }
    }
    return f[(1<<k)-1]<=n;
}
int main()
{
    n=read(),k=read();
    scanf("%s",s+1);
    int l=1,r=n;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",r);
    return 0;
}