What is the main approach for Count Substrings With K-Frequency Characters I?

Use a sliding window with a hash table to track character frequencies, expanding the right boundary and fixing the left to count valid substrings efficiently.

Can this problem be solved without a hash map?

Yes, but using a hash map for character counts allows efficient updates and avoids scanning each substring entirely.

What should I watch out for with k values larger than substring length?

No substrings will be valid in that case, so your code must handle k > current window size correctly.

How does fixing the left index help in this pattern?

Fixing the left index ensures substrings are counted exactly once, avoiding duplicates and simplifying frequency updates.

Is early stopping important for performance?

Yes, stopping expansion when no character can reach k prevents redundant checks and speeds up the sliding window approach.

#3325

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

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

给你一个字符串 s 和一个整数 k ，在 s 的所有子字符串中，请你统计并返回至少有一个字符至少出现 k 次的子字符串总数。子字符串是字符串中的一个连续、非空的字符序列。示例 1：输入： s = "abacb", k = 2 输出： 4 解释：符合条件的子字符串如下： "aba"…

哈希表字符串滑动窗口

题目描述

给你一个字符串 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 仅由小写英文字母组成。

lightbulb

解题思路

方法一：滑动窗口

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

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

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	complexity is O(n^2) in the worst case due to nested left-right iterations but often performs better with early stopping. Space complexity is O(1) or O(26) for the fixed alphabet hash map.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about edge cases where k is larger than substring length.
question_mark
Check if the candidate correctly maintains character counts in the sliding window.
question_mark
Expect recognition of early stopping to avoid unnecessary substring checks.

warning

常见陷阱

外企场景

error
Not updating the frequency map correctly when moving the left index.
error
Counting substrings multiple times by not fixing the left index properly.
error
Assuming all characters must appear k times instead of at least one.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count substrings where exactly one character appears k times.
arrow_right_alt
Find the longest substring where at least one character frequency is at least k.
arrow_right_alt
Apply the same method to strings with uppercase letters or digits, adjusting the hash map.

help

常见问题

外企场景

继续练习

#3306 元音辅音字符串计数 II #3305 元音辅音字符串计数 I #3298 统计重新排列后包含另一个字符串的子字符串数目 II