-----
有时候如果枚举起点超时，那么试试枚举终点。
枚举每一个i为终点(0<= i < n),且维护起点下标startPos
对于终点i，cnt[str[i]] ++, 如果小于等于k的话，那么以i为结尾的符合条件的字串的个数为i-startPos+1
如果大于k的话，改变区间下标startPos, 保证区间startPos-->i内相同字母的个数不超过k
while(true)
{
cnt[str[startPos]] --;
if(str[startPos] == str[i])
break;
startPos++;
}
startPos++;
#include <stdio.h>
#include <string.h>
const int N = + ;
typedef __int64 LL;
char str[N];
LL cnt[];
int main()
{
int t, k, i, n, startPos;
scanf("%d",&t);
LL ans;
while(t--)
{
startPos = ;
ans = ;
memset(cnt, , sizeof(cnt));
scanf("%s%d",str,&k);
n = strlen(str);
for(i=; i<n; ++i)
{
cnt[str[i]] ++;
if(cnt[str[i]] <= k)//当右指针往右移动1时，那么子串的个数就会增加，
//这些新增的子字串，都是因为str[i]的加入而形成的，即每个新增子串都有str[i]
//所以新增子串的为str[j->i] startPos<= j <= i, 即新增子串的个数为i-startPos+1
ans += i - startPos + ;
else
{
/*
如果新增一个字符str[i]使得cnt[str[i]] >= k
那么就要从区间[startPos,i)中找一个与str[i]相等的字符str[j]
使得startPos = j;
*/
while(true)
{
cnt[str[startPos]] --;
if(str[startPos] == str[i])
break;
startPos++;
}
startPos++;
ans += i - startPos + ;
}
}
printf("%I64d\n",ans);
}
return ;
}