首先,定义S,表示前k个字符出现的集合,用二进制来压缩。
接下来,推出dp1[S],表示集合为S的子串的最长长度。
然后根据dp1[S]再推出dp2[S],表示集合为S或S的子集的子串的最长长度。
最后答案就是max(dp2[S]*dp2[补(S)])
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int d[<<];
int main(){
int t,n,k;
char str[];
scanf("%d",&t);
while(t--){
scanf("%d%d%s",&n,&k,str);
memset(d,,sizeof(d));
for(int i=; i<n; ++i){
int s=;
for(int j=i; j<n; ++j){
s|=<<str[j]-'a';
d[s]=max(d[s],j-i+);
}
}
for(int i=; i<(<<k); ++i){
for(int j=; j<k ;++j){
if((i>>j)&) d[i]=max(d[i],d[i&(~(<<j))]);
}
}
int res=;
for(int i=; i<(<<k); ++i){
res=max(res,d[i]*d[(~i)&((<<k)-)]);
}
printf("%d\n",res);
}
return ;
}