$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(n)做法的思路，提供一种python实现

def check(start, end):
    cnt = 0
    for i in range(26):
        if lst[i][end-1] - (lst[i][start-2] if start >= 2 else 0) == k:
            cnt += 1
    return cnt

n, k = map(int,input().split(" "))
inp = input()
lst = [[0] * n for i in range(26)]
#n列，26行(第一列为0)
for i in range(26):
    letter = chr(ord('a') + i)
    for j in range(len(inp)):
        if letter == inp[j]:
            lst[i][j] = lst[i][j-1] + 1
        else:
            lst[i][j] = lst[i][j-1]
ans = 0
for i in range(1,27):
    length = i * k
    for j in range(length,n + 1):
        l = j - length + 1
        r = j
        if check(l, r) == i:
            ans += 1
print(ans)

n , k = map(int , input().split()) lst = input() count = 0 for i in range (1 , 27) :#枚举一个集合里面有几种元素 s = {}#集合 for j in range (0 , min(ik , n)) :#先取前几个元素作为滑动窗口 if lst[j] not in s : s[lst[j]] = 0 s[lst[j]] += 1 for j in range (min(ik , n) , n) : cc = 0 for a , b in s.items() : if b == k : cc += 1 if cc == i : count += 1 if lst[j] not in s : s[lst[j]] = 0 s[lst[j]] += 1 s[lst[j - i*k]] -= 1 #这里滑动窗口的这种写法可以让滑动窗口的时间复杂度降低至O（1） cc = 0#补上一段检测最后一个元素 for a , b in s.items() : if b == k : cc += 1 if cc == i : count += 1 print(count)

复杂度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)

直接前缀和预处理后以k倍数的区间长度进行前缀和查询即可,手算运行次数n^2 / k - 26 * n, 最坏情况运行7e9,一个n^2的算法,数据没有卡,极限时间900ms,可以直接过

const int N = 1e5 + 10;
int sum[26][N];
void solve() {
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = " " + s;
    for(int j = 1; j <= n ; j ++ ) {
        for(int i = 0 ; i < 26 ; i ++ ){
            sum[i][j] = sum[i][j - 1];
        }
        sum[s[j] - 'a'][j] ++ ;
    }
    ll ans = 0;
    for(int i = k ; i <= n; i += k ) {
        for(int x = i ; x <= n ; x ++ ){
            bool ok = false;
            for(int j = 0 ; j < 26 ; j ++ ) {
                if(sum[j][x] - sum[j][x - i] == 0)continue;
                if(sum[j][x] - sum[j][x - i] != k) {
//                  cout << (char)(j + 'a') << ' ' << x << ' ' << x - i<< endl;
//                  cout << sum[j][x] << ' ' << sum[j][x - i] << endl;
//                  ans ++ ;
                    ok = true;
                }
            }
            if(!ok) ans ++ ;
        }
    }
     cout << ans;
}