标签：DP \(B^+\)
阅读须知：本题解较为详细地讲述的该题解法的思路和来龙去脉，但篇幅较长，请耐心阅读。
Step 1 从题面获取信息
我们考虑，因为最大值最小，所以我们首先想到二分答案。
然后我们又看到 \(k \leq 17\) 这个限制，所以会想到可能是关于一个 \(2^k\) 之类的复杂度。
以上就是我们第一步从题目的数据范围中挖掘出来的一些思路。
Step 2 从暴力入手进行优化
我们二分答案 \(mid\) 之后，就只需要判断答案 \(mid\) 的可行性了，也就是说我们要判断是否每一种字母都能有 \(mid\) 长度的子串。
对于判断正确性显然有一种非常简单的暴力，就是枚举字母所确定的子串所出现的相对顺序，然后暴力 check 是否可行，这是 \(O(n\times k!)\) 的，但是显然不能通过这道题。
① 状态枚举的优化
这时，我们复杂度瓶颈在于花去太多时间在出现顺序的枚举（\(n!\)），而我们上文分析到的 \(2^k\) 显然他的一个很好的转化的终点。
那么为什么能转化呢，又如何转化呢？
为什么能：我们发现每次加进去一种字母的长为 \(mid\) 的段时，并不需要知道之前的字母的出现的顺序到底是什么，而我们的 \(n!\) 的暴力算法的顺序枚举显然会多出许多不必要的信息的枚举，这显然给了我们代码时间复杂度的优化空间。
如何转化：我们可以设 \(dp_S\) 表示让集合 \(S\) 中的所有字母都满足有长度为 \(mid\) 的子串的最短的前缀（显然前缀越短剩下的字母放完的可能性才更大）。
温馨提示：这里的前缀串在记录时为开区间
这下我们就将状态个数优化到了 \(2^k\)，\(O((n+k)2^k\log n)\) 是不能通过本题的，但是状态显然是已经优化到了极致，所以我们只能从转移上下手，尝试把 \(n\) 给干掉。
② 转移的优化
我们发现每个位置的转移的显然不需要依赖于当前的整个状态（数量：\(2^k\)），只需要依赖于当前需要加入哪种字母（数量：\(k\)）进入集合，所以说我们可以将原本的 \(n2^k\) 的转移变成 \(nk\) 。
显然地，你需要预处理转移数组 \(jump_{i,j}\) 表示原来的前缀串以 \(i\) 结束，满足入第 \(j\) 种字母的要求后，新的前缀串的最小的右端点的位置，这时需要倒序枚举（后面有解释），转移如下：
\[jump_{i,j} = \begin{cases} i+len & \forall i\leq k < i+len，s_j = 'a'+j~||~s_j = '?'\\ jump_{i+1,j} & otherwise \end{cases} \]而对于第一种转移的限制条件的判定，我们可以动态维护除了这一种字母、其他字母最左边出现的位置，这显然需要倒序枚举。
Step 3 思考实现细节并敲出代码
code:
#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8,MM = 20;
int dp[1 << MM];
int n,k;
char s[NN];//字符串
int jump[NN][MM];
int minp[MM];//第i种字母最左边出现的位置
int res[MM];//除第i种字母以外的其他字母最左边出现的位置
bool solve(int len){
memset(dp,0x3f,sizeof(dp));
memset(res,0x3f,sizeof(res));//初始化
for(int i = 0; i < k; ++i) minp[i] = n+1,jump[n+1][i] = n+2,jump[n+2][i] = n+2;//限定边界
for(int i = n; i >= 1; --i){
if(s[i] != '?'){//更新res
minp[s[i]-'a'] = i;
for(int j = 0; j < k; ++j){
if(s[i]-'a' == j) continue;
res[j] = i;
}
}
for(int j = 0; j < k; ++j){//转移
if(res[j] >= i+len) jump[i][j] = min(n+2,i+len);
else jump[i][j] = jump[i+1][j];
}
}
dp[0] = 1;
for(int i = 1; i < (1 << k); ++i){//DP转移
for(int j = 0; j < k; ++j)if(i >> j & 1){
dp[i] = min(jump[dp[i^(1 << j)]][j],dp[i]);
}
}
return dp[(1 << k)-1] <= n+1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> k;
cin >> s+1;
int l = 0,r = n,ans = 0;
while(l <= r){
int mid = (l + r) / 2;
if(solve(mid)) l = mid + 1,ans = mid;
else r = mid - 1;
}
printf("%d",ans);
}