给你一个字符串，然后问你这个字符串里面有多少个满足要求的子串，要求是每个子串相同字母出现的次数不能超过k。
思路：
这种题目做着比较有意思，而且不是很难（但自己还是嘚瑟，wa了好几次），这个题目的关键就是时间问题，对于每一个字母，我们只要加上以他为结尾的满足要求的子串个数就行了，假如前面的字母出现个数都没有超过k，那么当前的可以增加的和就是之前所有的字母个数，如果当前的字母个数出现超过k了，那么就得更新起点now（这个起点就是自己作为标记可行的最前位置），ans += 当前到now的字母的个数，具体的细节看下面代码，我写个核心的部分。
int mark[] 表示的是当前可满足的区间中每个字母出现的次数
int now 表示的是当前可满足区间的最前端的下标int now = 0;
for(int i = 0 ;i < n ;i ++)
{
if(++mark[str[i]] > k)
{
int nowid = now;
while(1)//这个别忘记了，一开始忘记了wa了好几次，挪动当前满足串的范围的时 { //候记得挪动出去的部分的字母出现次数减出去。
mark[str[nowid]] --;
if(str[nowid] == str[i]) break;
nowid ++;
}
now = nowid;
}
Ans += (i+1 - now);
}
#include<stdio.h> #include<string.h> char str[110000]; int mark[30]; int main () { int n ,t ,k; __int64 Ans ,i ,now; scanf("%d" ,&t); while(t--) { scanf("%s" ,str); scanf("%d" ,&k); n = strlen(str); Ans = now = 0; memset(mark ,0 ,sizeof(mark)); for(i = 0 ;i < n ;i ++) { if(++mark[str[i]-'a'] > k) { int nowi = now; while(1) { mark[str[nowi]-'a'] --; if(str[nowi] == str[i]) break; nowi ++; } now = nowi + 1; } Ans += (i - now + 1); } printf("%I64d " ,Ans); } return 0; }