What is the key strategy for Longest Substring with At Least K Repeating Characters?

The core strategy is using character frequency to split the string at invalid points, combined with sliding window updates to track valid substrings efficiently.

Can a sliding window alone solve this problem?

A sliding window alone may not capture all valid segments if characters below k are present, so combining it with divide-and-conquer ensures correctness.

What is the time complexity for this problem?

Time complexity is roughly O(n) on average, but depends on how many splits occur due to characters below the k threshold.

What data structures are most useful here?

Fixed-size arrays or hash maps for character counts are ideal, enabling quick frequency checks and efficient window updates.

How do I handle strings with no valid substring?

If no character meets the minimum repetition k, return 0 immediately to avoid unnecessary computation.

#395

Medium

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

LeetCode 题解工作台

至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。如果不存在这样的子字符串，则返回 0。示例 1：输入： s = "aaabb", k = 3 输出： 3 解释：最长子串为 "aaa" ，其中 'a' 重复了…

哈希表字符串分治滑动窗口

题目描述

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

如果不存在这样的子字符串，则返回 0。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

提示：

1 <= s.length <= 10⁴
s 仅由小写英文字母组成
1 <= k <= 10⁵

lightbulb

解题思路

方法一：分治

对于字符串 $s$ ，如果存在某个字符 $c$ ，其出现次数小于 $k$ ，则任何包含 $c$ 的子串都不可能满足题目要求。因此我们可以将 $s$ 按照每个不满足条件的字符 $c$ 进行分割，分割得到的每个子串都是原字符串的一个「子问题」，我们可以递归地求解每个子问题，最终的答案即为所有子问题的最大值。

时间复杂度 $O(n \times C)$ ，空间复杂度 $O(C^2)$ 。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 为字符集的大小。本题中 $C \leq 26$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        def dfs(l, r):
            cnt = Counter(s[l : r + 1])
            split = next((c for c, v in cnt.items() if v < k), '')
            if not split:
                return r - l + 1
            i = l
            ans = 0
            while i <= r:
                while i <= r and s[i] == split:
                    i += 1
                if i >= r:
                    break
                j = i
                while j <= r and s[j] != split:
                    j += 1
                t = dfs(i, j - 1)
                ans = max(ans, t)
                i = j
            return ans

        return dfs(0, len(s) - 1)

speed

复杂度分析

指标	值
时间	complexity is O(n) on average with recursive splits depending on character distribution. Space complexity is O(1) for counters if using fixed-size arrays for lowercase letters.
空间	\mathcal{O}(1)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate identifies characters below k as natural split points.
question_mark
Listen for mention of recursive divide-and-conquer or sliding window with frequency counters.
question_mark
Evaluate awareness of worst-case behavior when many characters fall below k.

warning

常见陷阱

外企场景

error
Counting frequencies globally without handling splits leads to incorrect substring lengths.
error
Not updating window counters dynamically can cause unnecessary rescanning.
error
Failing to handle edge cases where no valid substring exists, returning negative or wrong values.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest substring with at least k occurrences of exactly m distinct characters.
arrow_right_alt
Determine the number of substrings where each character occurs at least k times.
arrow_right_alt
Compute the longest substring allowing at most x characters to appear fewer than k times.

help

常见问题

外企场景

继续练习

#424 替换后的最长重复字符 #438 找到字符串中所有字母异位词 #567 字符串的排列