题解见官方题解，我这里只实现一下，其实官方题解好像有一点问题诶，比如
while( str[startPos] != str[i+1] ) cnt[str[startPos]]--, startPos++;
那个str[i+1]的话会越界。应该是这样： while(str[startPos] != str[i])
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #define lll __int64 using namespace std; #define N 100007 char ss[N]; int cnt[29]; int main() { int len,k,i,t; scanf("%d",&t); while(t--) { memset(ss,0,sizeof(ss)); memset(cnt,0,sizeof(cnt)); ss[0] = ‘$‘; scanf("%s",ss+1); len = strlen(ss+1); scanf("%d",&k); int s = 1; lll ans = 0; for(i=1;i<=len;i++) { cnt[ss[i]-‘a‘]++; if(cnt[ss[i]-‘a‘] > k) { while(ss[s] != ss[i]) cnt[ss[s]-‘a‘]--, s++; cnt[ss[s]-‘a‘]--, s++; } ans += i-s+1; } printf("%I64d\n",ans); } return 0; }
官方题解：
原文：http://www.cnblogs.com/whatbeg/p/3999202.html
