M3325.字符至少出现 K 次的子字符串 I

sliding window, https://leetcode.cn/problems/count-substrings-with-k-frequency-characters-i/

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

这是一个典型的双指针（滑动窗口）问题。

题目分析

我们需要统计满足以下条件的子字符串数量：该子字符串中至少有一个字符出现的次数大于等于 k。

关键性质： 对于一个固定的起始位置 left，如果子字符串 s[left:right+1] 已经满足条件（某个字符出现了 k 次），那么任何以 left 开头且更长的子字符串（如 s[left:right+2], s[left:right+3], ..., s[left:n]）也一定满足条件。

解题思路

我们可以使用滑动窗口来高效地统计：

维护一个窗口 [left, right] 和一个频率数组（或哈希表）来记录窗口内每个字符出现的次数。
不断向右移动 right 指针，将新字符加入窗口。
每当窗口内存在某个字符的频率达到 k 时：
- 此时，所有以当前 left 为起点，且终点在 right 及其之后的子字符串都满足条件。这些子字符串的数量为 n - right（其中 n 是字符串长度）。
- 将这个数量累加到结果中。
- 然后尝试收缩左边界 left，并更新频率数组，看看收缩后的新窗口是否依然满足条件。
为了高效判断“是否存在字符频率 $\geq k$ ”，我们可以维护一个变量 valid_chars，记录当前窗口内有多少种字符的频率达到了 k。

代码实现

python

class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        ans = 0
        left = 0
        # 记录窗口内每个字符（a-z）出现的次数
        cnt = [0] * 26
        # 记录当前窗口内有多少个字符的出现次数 >= k
        valid_chars = 0
        
        for right in range(n):
            # 1. 扩大窗口：将右侧字符加入
            idx_r = ord(s[right]) - ord('a')
            cnt[idx_r] += 1
            # 如果该字符出现次数刚好达到 k，则满足条件的字符种类加 1
            if cnt[idx_r] == k:
                valid_chars += 1
            
            # 2. 当窗口满足条件时（至少有一个字符出现次数 >= k）
            while valid_chars > 0:
                # 此时从 left 开始，终点在 [right, n-1] 范围内的所有子串都符合条件
                # 数量为：(n - 1) - right + 1 = n - right
                ans += (n - right)
                
                # 3. 缩小窗口：移动左指针
                idx_l = ord(s[left]) - ord('a')
                # 如果该字符出现次数原本是 k，移除它后就不再满足 >= k
                if cnt[idx_l] == k:
                    valid_chars -= 1
                cnt[idx_l] -= 1
                left += 1
                
        return ans

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是字符串的长度。虽然有嵌套的 while 循环，但 left 和 right 指针都各自只从 $0$ 遍历到 $n - 1$ ，每个字符最多进出窗口各一次。
空间复杂度： $O (1)$ 或 $O (| Σ |)$ ，其中 $| Σ |$ 是字符集的大小（本题为 26）。我们只使用了一个固定长度的数组。

简单来说：滑动窗口是双指针技术的一种特定形式。
你可以这样理解它们的关系：双指针是一个大类，而滑动窗口是其中的一个子类。
为了让你彻底搞清楚，我们可以把双指针分为三种常见的类型：
1. 滑动窗口 (Sliding Window) —— 本题所属类型
特点：两个指针（通常叫 left 和 right）向同一个方向移动。
范围：两个指针之间的内容 [left, right] 构成一个“窗口”。我们关注的是这个窗口内部的元素总和、频率或状态。
动作：right 不断向右扩大窗口，当窗口满足某种条件时，left 向右移动缩小窗口。
适用场景：求子数组、子字符串、连续区间的问题。
本题：我们维护 left 和 right 之间的字符频率。当频率满足 $K$ 次时，这个“窗口”就是一个合法的解的基础。
2. 对撞指针 (Opposite Direction)
特点：两个指针从两端向中间移动（一个在开头，一个在结尾）。
动作：left++，right--，直到它们相遇。
适用场景：
反转字符串/数组。
判断回文字符串。
有序数组的二数之和（Two Sum）。
3. 快慢指针 (Fast and Slow Pointers)
特点：两个指针同向移动，但移动速度不同。
适用场景：
判断链表是否有环（龟兔赛跑算法）。
寻找链表的中点。
删除有序数组中的重复项。
为什么这一题叫“滑动窗口”？
因为你在处理字符串时：
你关注的是连续的子序列（即窗口）。
窗口的右边界 right 带着“新成员”进来。
窗口的左边界 left 踢掉“老成员”出去。
这个窗口像是在字符串上从左往右“滑动”一样。
总结
所有滑动窗口都是双指针。
但双指针不一定是滑动窗口（比如判断回文时的对撞指针，两个指针之间并没有一个我们需要维护的“窗口”概念）。
在解决类似“统计子字符串/子数组”的问题时，只要看到“连续”和“至少/至多/最长/最短”这类字眼，第一时间就应该想到双指针里的滑动窗口。

M3325.字符至少出现 K 次的子字符串 I ​

M3325.字符至少出现 K 次的子字符串 I