comments	difficulty	edit_url	tags
true	困难	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3329.Count%20Substrings%20With%20K-Frequency%20Characters%20II/README.md	哈希表 字符串 滑动窗口

3329. 字符至少出现 K 次的子字符串 II 🔒

English Version

题目描述

给你一个字符串 s 和一个整数 k，在 s 的所有 子字符串 中，请你统计并返回 至少有一个 字符 至少出现 k 次的子字符串总数。

 

示例 1：

输入： s = "abacb", k = 2

输出： 4

解释：

符合条件的子字符串如下：

• "aba"（字符 'a' 出现 2 次）。
• "abac"（字符 'a' 出现 2 次）。
• "abacb"（字符 'a' 出现 2 次）。
• "bacb"（字符 'b' 出现 2 次）。

示例 2：

输入： s = "abcde", k = 1

输出： 15

解释：

所有子字符串都有效，因为每个字符至少出现一次。

 

提示：

• 1 <= s.length <= 3 * 105
• 1 <= k <= s.length
• s 仅由小写英文字母组成。

 

解法

方法一：滑动窗口

我们可以枚举子字符串的右端点，然后用一个滑动窗口维护子字符串的左端点，使得滑动窗口内的子字符串中的每个字符出现次数都小于 $k$。

我们可以用一个数组 $\mathit{\text{cnt}}$ 维护滑动窗口内的每个字符的出现次数，然后用一个变量 $\mathit{\text{l}}$ 维护滑动窗口的左端点，用一个变量 $\mathit{\text{ans}}$ 维护答案。

当我们枚举右端点时，我们可以将右端点的字符加入滑动窗口，然后判断滑动窗口内右端点的字符出现次数是否大于等于 $k$，如果是，则将左端点的字符移出滑动窗口，直到滑动窗口内的每个字符出现次数都小于 $k$。此时，对于左端点为 $[0,..l-1]$，且右端点为 $r$ 的子字符串，都满足题目要求，因此答案加上 $l$。

枚举结束后，返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(|\mathrm{\Sigma }|)$，其中 $\mathrm{\Sigma }$ 是字符集，这里是小写字母集合，因此 $|\mathrm{\Sigma }|=26$。

Python3

class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        cnt = Counter()
        ans = l = 0
        for c in s:
            cnt[c] += 1
            while cnt[c] >= k:
                cnt[s[l]] -= 1
                l += 1
            ans += l
        return ans

Java

class Solution {
    public long numberOfSubstrings(String s, int k) {
        int[] cnt = new int[26];
        long ans = 0;
        for (int l = 0, r = 0; r < s.length(); ++r) {
            int c = s.charAt(r) - 'a';
            ++cnt[c];
            while (cnt[c] >= k) {
                --cnt[s.charAt(l) - 'a'];
                l++;
            }
            ans += l;
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long numberOfSubstrings(string s, int k) {
        int n = s.size();
        long long ans = 0, l = 0;
        int cnt[26]{};
        for (char& c : s) {
            ++cnt[c - 'a'];
            while (cnt[c - 'a'] >= k) {
                --cnt[s[l++] - 'a'];
            }
            ans += l;
        }
        return ans;
    }
};

Go

func numberOfSubstrings(s string, k int) (ans int64) {
	l := 0
	cnt := [26]int{}
	for _, c := range s {
		cnt[c-'a']++
		for cnt[c-'a'] >= k {
			cnt[s[l]-'a']--
			l++
		}
		ans += int64(l)
	}
	return
}

TypeScript

function numberOfSubstrings(s: string, k: number): number {
    let [ans, l] = [0, 0];
    const cnt: number[] = Array(26).fill(0);
    for (const c of s) {
        const x = c.charCodeAt(0) - 97;
        ++cnt[x];
        while (cnt[x] >= k) {
            --cnt[s[l++].charCodeAt(0) - 97];
        }
        ans += l;
    }
    return ans;
}