这个题刚开时毫无头绪，后来才知道这种算法。
这个题有个漏洞，不同位置截出来的相同子串，算是两个子串。
其他的没什么了，注意 long long int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int N,pre,n,sum,x;
int a[27];
char s[100010];

int main() {
    scanf("%d",&N);
    while(N--) {
        scanf("%s",&s);
        scanf("%d",&n);
        pre = 0;
        long long sum = 0;
        memset(a,0,sizeof(a));
        x = strlen(s);
        for(int i = 0; i < x; i++) {
            a[s[i]-'a']++;
            while(a[s[i]-'a']>n) {
                a[s[pre]-'a']--;
                pre++;
            }
            sum += i - pre + 1;
        }
        printf("%lld\n",sum);
    }
    return 0;
}