$O(n^3)$ 做法

枚举所有区间，对每个区间依次验证每种字符的数量是否为 $k$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
string s;
bool check(int l,int r){
	int cnt[30]={0};
	for(int i=l;i<=r;i++){
		cnt[s[i]-'a']++;
	}
	for(int i=0;i<=25;i++){
		if(cnt[i]!=0&&cnt[i]!=k) return false;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>k;
	cin>>s;
	s=" "+s;
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			if(check(i,j)) ans++;
		}
	}
	cout<<ans;
}

$O(n^2)$ 做法

对于上一种做法，check 函数的作用为统计 $l\sim r$ 的区间中每种字符的数量，然后再验证每种字符数量是否恰好为 $k$。

我们可以利用前缀和预处理出每种字符的数量，直接用前缀和计算区间中每种字符的数量即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, k;
string s;
int pre[26][N]; 

bool check(int l, int r) {
    for (int c = 0; c < 26; c++) {
        int count = pre[c][r] - pre[c][l - 1];
        if (count != 0 && count != k)
            return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    cin >> s;
    s = " " + s; 

    for (int i = 1; i <= n; i++) {
        for (int c = 0; c < 26; c++)
            pre[c][i] = pre[c][i - 1];
        pre[s[i] - 'a'][i]++;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (check(i, j))
                ans++;
        }
    }

    cout << ans << '\n';
}

$O(n)$ 做法

注意到题目要求，每种字符数量要恰好为 $k$。则符合题目要求的区间长度其实只有 $k,2k,3k,...,25k,26k$。

我们枚举区间长度，然后用前缀和统计每个区间的字符数量再验证即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int sum[N][30];
int n,k;
int check(int l,int r){
	int ans=0;
	for(int i=1;i<=26;i++){	
		if(sum[r][i]-sum[l-1][i]==k) ans++;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>k;
	string s;
	cin>>s;
	s=" "+s;
	for(int i=1;i<=n;i++){
		int t=s[i]-'a'+1;
		for(int j=1;j<=26;j++){
			sum[i][j]=sum[i-1][j];
		}
		sum[i][t]++;
	}
	int ans=0;
	for(int i=1;i<=26;i++){
		for(int j=k*i;j<=n;j++){
			int l=j-(k*i)+1,r=j;
			if(check(l,r)==i){
				ans++;
			}
		}
	}
	cout<<ans;
}

复杂度O（26**2*n）

import os
import sys
n, k = map(int, input().split())
str = input()
ls = 'abcdefghijklmnopqrstuvwxyz'
lsi = {s: i for i, s in enumerate(ls)}
c = [[0] * 26]
for i in range(n):
    c.append([c[-1][i] for i in range(26)])
    s = str[i]
    c[-1][lsi[s]] = c[-2][lsi[s]] + 1
r = 0
for i in range(n - k + 1):
    for j in range(i + k, i + k * 26 + 1, k):
        if j >= len(c):
            break
        f = 1
        for s in range(26):
            if c[j][s] - c[i][s] > k:
                f = -1
                break
            elif 0 < c[j][s] - c[i][s] < k:
                f = 0
                break
        if f == 1:
            r += 1
        elif f == -1:
            break
print(r)