题意略。
巧妙的尺取法。我们来枚举每个字符str[i]，计算以str[i]为结尾的符合题意的串有多少个。那么我们需要处理出str[i]的左边界j,在[j,i]之间的串均为符合题意的
串，那么str[i + 1]能否利用str[i]的处理结果呢？是可以的。str[i + 1]的左边界 >= str[i]的左边界。由此可以使用尺取。
#include<bits/stdc++.h>
#define maxn 100050
using namespace std;
typedef long long LL; char str[maxn];
int cnt[];
int T,K; void init(){
memset(cnt,,sizeof(cnt));
} int main(){
scanf("%d",&T);
while(T--){
init();
scanf("%s",str);
scanf("%d",&K);
LL len = strlen(str);
LL ans = ;
int head = ;
for(LL i = ;i < len;++i){
++cnt[str[i] - 'a'];
ans += (i - head + );
while(cnt[str[i] - 'a'] > K){
--cnt[str[head] - 'a'];
++head;
ans -= ;
}
}
printf("%lld\n",ans);
}
return ;
}
/*
1
aabbccccd
2
*/