LeetCode 395 至少有 K 个重复字符的最长子串
文章目录
摘要
这道题要在字符串里找「最长的一段子串」，且这段子串里出现的每个字符，出现次数都不少于 k。例如 s = "ababbc", k = 2 时，"ababb" 里 a 出现 2 次、b 出现 3 次，都 ≥ 2，长度 5 就是答案；而整串里有 c 只出现 1 次，所以不能整段算。
做法是分治：先统计当前段里每个字符出现次数，把「出现次数小于 k」的字符当作「分隔符」——任何合法子串都不能包含它们，否则那个字符次数一定不够。用这些分隔符把当前串拆成多段，对每一段递归求「至少 k 次」的最长子串长度，取最大值；若当前段里没有这种分隔符，说明当前段每个字符都 ≥ k 次，直接返回段长。下面用 Swift 实现并说明细节。
描述
给你一个字符串 s 和一个整数 k，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k。返回这一子串的长度；如果不存在这样的子串则返回 0。
示例 1：
输入： s = "aaabb", k = 3 输出： 3 解释： 最长子串为 "aaa" ，其中 'a' 重复了 3 次。'b' 只有 2 次，不能包含在合法子串里。 示例 2：
输入： s = "ababbc", k = 2 输出： 5 解释： 最长子串为 "ababb" ，其中 'a' 重复了 2 次，'b' 重复了 3 次。'c' 只出现 1 次，所以含 c 的段都不合法。 提示：
1 <= s.length <= 10^4s仅由小写英文字母组成1 <= k <= 10^5
核心思路：出现次数小于 k 的字符一定会「隔断」合法子串，所以按这些字符把串拆开，在每一段里递归求答案，再取最大值；若某段内已经没有「次数 < k」的字符，整段就是合法的，长度为该段长度。
题解答案
classSolution{funclongestSubstring(_ s:String,_ k:Int)->Int{let arr =Array(s)if arr.isEmpty || k > arr.count {return0}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 =0var start =0for i in0..<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 大于串长的提前返回，以及遍历结束后对最后一段的递归，即可正确得到最长合法子串长度。