我是如何嫖大佬题解的
//随便找一个字符串,比如abcdcbef,按照算法自己模拟一遍就恍然大悟了!
18行是核心
嫖了别人的一个解答,
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
char s[N];
int alp[26];
int main(){
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s);
int ans=N;
for(int i=0,j=0;i<n;i++){
int x=s[i]-'a';
alp[x]++;//当前字母出现的次数
//非常巧妙地算法!记住!虽然还不是很理解
while(alp[x]==k && s[j]!=s[i] || alp[x]>k)
alp[s[j++]-'a']--;//j记录初始k头
//如果出现第k次,就不断地从前面朝后减1,直到找到头、
//道理就在于,头之前的那些字母都可以舍去了
//出现第k+1次 ,那一个字母自己比较,就不用找头
//abcdcbef自己模拟一遍就恍然大悟了!
if(alp[x]>=k)
ans=min(ans,i-j+1);
//这个字母还没到k次,就不计算
}
if(ans==N)
ans=-1;
printf("%d",ans);
return 0;
}

京公网安备 11010502036488号