Swift算法
LeetCode 395 至少有 K 个重复字符的最长子串
讲解 LeetCode 395 题解法。题目要求找出字符串中最长子串，使得子串中每个字符出现次数均不少于 k。核心思路采用分治策略：统计当前段字符频次，将出现次数小于 k 的字符作为分隔符将字符串切分为多段，对每段递归求解。若某段内无此类字符，则整段合法。代码使用 Swift 实现，包含复杂度分析及示例验证。
讲解 LeetCode 395 题解法。题目要求找出字符串中最长子串，使得子串中每个字符出现次数均不少于 k。核心思路采用分治策略：统计当前段字符频次，将出现次数小于 k 的字符作为分隔符将字符串切分为多段，对每段递归求解。若某段内无此类字符，则整段合法。代码使用 Swift 实现，包含复杂度分析及示例验证。
这道题要在字符串里找「最长的一段子串」，且这段子串里出现的每个字符，出现次数都不少于 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」的字符，整段就是合法的，长度为该段长度。
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 次」。这类字符相当于「禁区」：任何跨过它们的子串都会把该字符包含进去，从而不合法。因此用它们做分隔符，把当前串切成多段，合法子串只会出现在某一段内部，不会横跨分隔符。
先对当前段做一次字符计数，得到 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 很大时不会死循环，也不会无意义递归。
整串计数：a=3, b=2。出现次数 < 3 的只有 b，splitSet = {b}。按 b 切分成 'aaa' 和 ''。对 'aaa' 递归：计数只有 a=3，splitSet 为空，返回 3。对 '' 返回 0。所以 ans = max(3, 0) = 3。
整串计数：a=2, b=3, c=1。次数 < 2 的为 c，splitSet = {c}。按 c 切分成 'ababb' 和 ''。对 'ababb' 递归：a=2, b=3，都 ≥ 2，splitSet 为空，返回 5。对 '' 返回 0。所以 ans = 5。
合法最长子串为 'aaa'，长度为 3。
合法最长子串为 'ababb'，长度为 5。
s = 'aabbcc', k = 2，每个字符都出现 2 次，整串合法，返回 6。
s = 'abc', k = 2，每个字符只出现 1 次，无法满足「每个字符至少 2 次」，返回 0。
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 大于串长的提前返回，以及遍历结束后对最后一段的递归，即可正确得到最长合法子串长度。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online