1 while(true)2 {3 cnt[str[startPos]] --;4 if(str[startPos] == str[i])5 break;6 startPos++;7 }8 startPos++;

 1 #include <stdio.h> 2 #include <string.h> 3 const int N = 100000 + 10; 4 typedef __int64 LL; 5 char str[N]; 6 LL cnt[200]; 7 int main() 8 { 9     int t, k, i, n, startPos;10     scanf("%d",&t);11     LL ans;12     while(t--)13     {    14         startPos = 0;15         ans = 0;16         memset(cnt, 0, sizeof(cnt));17         scanf("%s%d",str,&k);18         n = strlen(str);19         for(i=0; i<n; ++i)20         {21             cnt[str[i]] ++;22             if(cnt[str[i]] <= k)//当右指针往右移动1时，那么子串的个数就会增加，23                 //这些新增的子字串，都是因为str[i]的加入而形成的，即每个新增子串都有str[i]24                 //所以新增子串的为str[j->i]    startPos<= j <= i, 即新增子串的个数为i-startPos+125                 ans += i - startPos + 1;26             else27             {28                 /*29                 如果新增一个字符str[i]使得cnt[str[i]] >= k30                 那么就要从区间[startPos,i)中找一个与str[i]相等的字符str[j]31                 使得startPos = j;32                 */33                 while(true)34                 {35                     cnt[str[startPos]] --;36                     if(str[startPos] == str[i])37                         break;38                     startPos++;39                 }40                 startPos++;41                 ans += i - startPos + 1;42             }43         }44         printf("%I64d\n",ans);45     }46     return 0;47 }