题目大意：
给定一个字符串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
",r);
return 0;
}