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

• 1 <= s.length <= 10^4
• s 仅由小写英文字母组成
• 1 <= k <= 10^5

核心思路：出现次数小于 k 的字符一定会「隔断」合法子串，所以按这些字符把串拆开，在每一段里递归求答案，再取最大值；若某段内已经没有「次数 < k」的字符，整段就是合法的，长度为该段长度。

题解答案

class Solution {
    func longestSubstring(_ s: String, _ k: Int) -> Int {
        let arr = Array(s)
        if arr.isEmpty || k > arr.count {
            return 0
        }
        var count: [Character: Int] = [:]
        for c in arr {
            count[c, default: 0] += 1
        }
        let splitSet = Set(count.filter { $0.value < k }.map { $0.key })
        if splitSet.isEmpty {
            return arr.count
        }
        var ans = 0
        var start = 0
        for i in 0..<arr.count {
            if splitSet.contains(arr[i]) {
                if start < i {
                    ans = max(ans, longestSubstring(String(arr[start..<i]), k))
                }
                start = i + 1
            }
        }
        if start < arr.count {
            ans = max(ans, longestSubstring(String(arr[start..<arr.count]), k))
        }
        return ans
    }
}

题解代码分析

为什么要找「出现次数小于 k」的字符

合法子串的定义是：子串里出现的每一个字符，在该子串内都至少出现 k 次。所以一旦某个字符在整个当前段里出现次数就小于 k，它就不可能出现在任何合法子串里，否则光它自己就不满足「至少 k 次」。这类字符相当于「禁区」：任何跨过它们的子串都会把该字符包含进去，从而不合法。因此用它们做分隔符，把当前串切成多段，合法子串只会出现在某一段内部，不会横跨分隔符。

分治在做什么

先对当前段做一次字符计数，得到 count；再筛出 count[c]! < k 的字符放进 splitSet。若 splitSet 为空，说明当前段里每个字符出现次数都 ≥ k，整段合法，直接返回 arr.count。否则遍历当前段，遇到 splitSet 里的字符就说明遇到分隔符：先对「从 start 到当前分隔符之前」的一段递归求 longestSubstring，用结果更新 ans，再把 start 移到分隔符后一位。遍历结束后，别忘了从最后一个分隔符到串尾还有一段，再递归这一段并更新 ans。最终返回的 ans 就是当前段内「至少 k 次」的最长子串长度。

边界与提前返回

若 arr.isEmpty 或 k > arr.count，不可能有字符出现 k 次，直接返回 0。这样递归到很短的子串或 k 很大时不会死循环，也不会无意义递归。

示例 1 简要过程：s = 'aaabb', k = 3

整串计数：a=3, b=2。出现次数 < 3 的只有 b，splitSet = {b}。按 b 切分成 'aaa' 和 ''。对 'aaa' 递归：计数只有 a=3，splitSet 为空，返回 3。对 '' 返回 0。所以 ans = max(3, 0) = 3。

示例 2 简要过程：s = 'ababbc', k = 2

整串计数：a=2, b=3, c=1。次数 < 2 的为 c，splitSet = {c}。按 c 切分成 'ababb' 和 ''。对 'ababb' 递归：a=2, b=3，都 ≥ 2，splitSet 为空，返回 5。对 '' 返回 0。所以 ans = 5。

示例测试及结果

示例 1：s = 'aaabb', k = 3

合法最长子串为 'aaa'，长度为 3。

示例 2：s = 'ababbc', k = 2

合法最长子串为 'ababb'，长度为 5。

示例 3：整串都合法

s = 'aabbcc', k = 2，每个字符都出现 2 次，整串合法，返回 6。

示例 4：无合法子串

s = 'abc', k = 2，每个字符只出现 1 次，无法满足「每个字符至少 2 次」，返回 0。

示例 5：k 大于串长

s = 'aa', k = 3，串长 2 < k，返回 0。

时间复杂度

最坏情况下，每次递归都只去掉一个字符（例如某字符只出现一次当分隔符），递归深度 O(n)，每层统计和分割 O(n)，整体 O(n^2)。平均情况下分割更均匀，会好很多。字符集只有 26 个小写字母，计数和 splitSet 规模可视为常数。

空间复杂度

递归栈深度最坏 O(n)；每层用到的 count、splitSet 以及子串的拷贝，规模与当前段长相关。整体可视为 O(n) 的栈与临时空间。

实际应用场景

类似「每个元素都满足某条件的最长连续段」的问题，在规则校验、日志或序列分析里会碰到。例如：找一段连续记录里每种类型都至少出现若干次的窗口、或满足「每种标签都达到最低出现次数」的最长区间，都可以用同一思路：用不满足条件的元素做分隔，再在段内递归或做滑动窗口。

总结

「至少有 K 个重复字符的最长子串」可以分治做：先统计当前段字符次数，把出现次数小于 k 的字符当作分隔符切段，对每一段递归求答案并取最大值；若当前段没有这类字符，整段合法，返回段长。实现时注意空串和 k 大于串长的提前返回，以及遍历结束后对最后一段的递归，即可正确得到最长合法子串长度。