题目描述

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

子字符串 是字符串中的一个连续、 非空 的字符序列。

样例

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

输出： 4

解释：

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

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

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

输出： 15

解释：

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

限制

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

算法

(双指针) $O(n + |\Sigma|)$

1. 对于每一个位置 $i$，找到尽可能小的位置 $j$，满足区间 $[j, i]$ 构成的子串 不 满足条件。
2. 注意到，随着 $i$ 的移动，$j$ 是单调不减的，所以考虑使用双指针。
3. 在遍历过程中，维护当前区间 $[j, i]$ 中每个字母的出现次数，以及有多少个字母满足至少 $k$ 个。
4. 如果发现区间满足条件了，则不断移动 $j$ 直到不满足条件。
5. 以 $i$ 为结尾满足条件的区间有 $[0, i], [1, i], \dots, [j - 1, i]$ 共 $j$ 个。

时间复杂度

• 预处理数组的时间复杂度为 $O(|\Sigma|)$。
• 每个位置仅被遍历两次，每次遍历的操作复杂度为常数。
• 故总时间复杂度为 $O(n + |\Sigma|)$。

空间复杂度

• 需要 $O(|\Sigma|)$ 的额外空间存储当前区间每个字母的出现次数。

C++ 代码

class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        const int n = s.size();

        int ans = 0;
        vector<int> cnt(26, 0);
        int m = 0;

        for (int i = 0, j = 0; i < n; i++) {
            ++cnt[s[i] - 'a'];
            if (cnt[s[i] - 'a'] == k)
                ++m;

            while (m > 0) {
                --cnt[s[j] - 'a'];
                if (cnt[s[j] - 'a'] == k - 1)
                    --m;

                ++j;
            }

            ans += j;
        }

        return ans;
    }
};