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

难度困难

题目描述

给你一个字符串 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 * 10⁵
1 <= k <= s.length
s 仅由小写英文字母组成。

解法

方法一：滑动窗口

思考

与 I 同一计数问题，但 \(n \le 3 \times 10^5\)，必须保持线性窗口。

「某个字符出现不少于 \(k\) 次」对左端点单调，维护所有计数都小于 \(k\) 的最长后缀即可。

实现与 I 相同：右端纳入后若某字符达到 \(k\) 则右移左端，答案累加 \(l\)。

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

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

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

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

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

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

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

题目描述

解法

方法一：滑动窗口

评论