**题意：

     给你一个字符串，然后问你这个字符串里面有多少个满足要求的子串，要求是每个子串相同字母出现的次数不能超过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
#include
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\n" ,Ans); } return 0; }