LeetCode 395题解析：分治法求解最长K重复字符子串-北京尧图网络

1. 问题背景与理解LeetCode 395题至少有 K 个重复字符的最长子串是一个经典的字符串处理问题考察我们对分治算法和递归思想的理解。题目要求我们找到给定字符串中最长的子串其中每个字符的出现次数都不少于k次。我第一次遇到这个问题时直觉上觉得可以用滑动窗口解决但实际尝试后发现常规的滑动窗口方法会遇到困难。这促使我深入思考更合适的解法。经过几次失败的尝试后我意识到这个问题需要结合分治思想和递归来解决。2. 问题分析与解法思路2.1 问题重述给定一个字符串s和一个整数k我们需要找到s的最长子串的长度使得该子串中的每个字符的出现次数都不少于k。例如输入s aaabb, k 3输出3解释最长子串为aaa其中a出现3次。2.2 核心难点解析这个问题的难点在于如何高效地处理字符串中不符合条件的字符。直接暴力解法的时间复杂度会很高无法通过LeetCode的测试用例。关键观察点如果一个字符在整个字符串中的总出现次数小于k那么它不可能出现在任何符合条件的子串中这样的字符实际上可以作为分隔符将原字符串分割成多个子问题我们可以递归地处理这些子问题最终合并结果2.3 分治算法设计基于以上观察我们可以设计如下分治算法统计字符串中每个字符的出现频率找到第一个出现频率小于k的字符分割点以该字符为分割点将字符串分成左右两部分递归地在左右子字符串中寻找符合条件的子串返回左右结果中的较大值如果字符串中所有字符的出现频率都≥k则整个字符串就是符合条件的子串直接返回其长度。3. 代码实现与详细解析3.1 基础实现def longestSubstring(s: str, k: int) - int: if len(s) k: return 0 # 统计字符频率 freq {} for c in s: freq[c] freq.get(c, 0) 1 # 找到第一个不符合条件的字符作为分割点 split None for i, c in enumerate(s): if freq[c] k: split c break # 如果没有分割点说明整个字符串都符合条件 if not split: return len(s) # 分割字符串并递归处理 max_len 0 for substr in s.split(split): max_len max(max_len, longestSubstring(substr, k)) return max_len3.2 优化实现上面的基础实现可以进一步优化减少不必要的字符串分割操作def longestSubstring(s: str, k: int) - int: if len(s) k: return 0 freq {} for c in s: freq[c] freq.get(c, 0) 1 # 收集所有不符合条件的字符 splits [c for c in freq if freq[c] k] if not splits: return len(s) # 使用正则表达式一次性分割所有不符合条件的字符 import re pattern |.join(re.escape(c) for c in splits) substrings re.split(pattern, s) max_len 0 for substr in substrings: max_len max(max_len, longestSubstring(substr, k)) return max_len3.3 复杂度分析时间复杂度O(n^2) 最坏情况下如字符串中字符都唯一且k1每次递归处理n-1长度的字符串空间复杂度O(n) 递归栈的深度4. 算法正确性证明为了验证我们算法的正确性可以考虑以下几点基本情况当字符串长度小于k时显然没有符合条件的子串递归情况当存在出现次数小于k的字符时任何符合条件的子串都不能包含该字符因此可以安全地分割合并情况最终结果是左右子问题结果的较大值这保证了我们找到的是全局最优解终止条件当字符串中所有字符出现次数都≥k时整个字符串就是解5. 边界条件与测试用例5.1 常见边界情况空字符串或k0字符串中所有字符都相同字符串中所有字符都唯一k1的特殊情况非常长的字符串测试算法效率5.2 测试用例示例test_cases [ (aaabb, 3, 3), (ababbc, 2, 5), (abcde, 2, 0), (, 1, 0), (a*10000, 1, 10000), (abcdefghijklmnopqrstuvwxyz, 1, 26), (aabbbcccdddeee, 3, 9) ] for s, k, expected in test_cases: assert longestSubstring(s, k) expected6. 性能优化与替代解法6.1 滑动窗口法的局限性很多同学会首先尝试滑动窗口法但发现难以处理窗口内字符频率的统计。主要困难在于不知道窗口应该包含哪些字符无法确定何时扩展/收缩窗口难以同时满足所有字符频率≥k的条件6.2 改进的滑动窗口法实际上这个问题可以使用滑动窗口法解决但需要一些技巧限定窗口中不同字符的数量t从1到26遍历对于每个t使用滑动窗口统计恰好包含t种字符的子串检查这些子串是否满足所有字符频率≥k记录满足条件的最大子串长度这种方法的时间复杂度是O(26n)O(n)比递归解法更高效。6.3 滑动窗口实现def longestSubstring(s: str, k: int) - int: max_len 0 for t in range(1, 27): # 尝试1到26种不同字符 left 0 freq [0] * 26 unique total 0 # unique:当前窗口不同字符数, total:满足≥k的字符数 for right in range(len(s)): idx ord(s[right]) - ord(a) if freq[idx] 0: unique 1 freq[idx] 1 if freq[idx] k: total 1 while unique t: left_idx ord(s[left]) - ord(a) if freq[left_idx] k: total - 1 freq[left_idx] - 1 if freq[left_idx] 0: unique - 1 left 1 if unique total t: max_len max(max_len, right - left 1) return max_len7. 实际应用与扩展7.1 实际应用场景这类字符串处理问题在实际中有多种应用基因序列分析寻找满足特定重复模式的DNA片段文本挖掘提取高频词汇组成的连续文本段数据清洗识别并处理异常或低频字符序列7.2 问题变种至少包含m个不同字符且每个字符至少出现k次的最长子串最多包含m个不同字符且每个字符至少出现k次的最长子串允许最多x个字符不满足条件的最长子串7.3 学习建议先理解分治法的基本思想再应用到字符串问题上从简单例子入手手动模拟算法执行过程比较不同解法的时间/空间复杂度尝试自己设计测试用例包括边界情况8. 常见错误与调试技巧8.1 常见错误递归终止条件不正确导致无限递归字符串分割时处理不当丢失部分子串频率统计错误特别是Unicode字符的处理没有正确处理k0或空字符串的情况8.2 调试技巧添加打印语句跟踪递归过程和变量状态对小规模测试用例手动计算预期结果使用LeetCode的测试用例失败信息定位问题比较递归和滑动窗口两种解法的结果是否一致8.3 性能调优对于Python避免频繁的字符串拼接和分割使用更高效的数据结构统计字符频率对于滑动窗口法提前终止不必要的循环考虑使用记忆化技术优化递归解法9. 算法选择建议根据不同的场景可以选择不同的解法对于一般面试或编程竞赛分治递归解法更容易理解和实现对于性能要求高的场景滑动窗口解法更优对于特别长的字符串可能需要考虑并行处理或更高级的算法在实际应用中还需要考虑字符串的预期长度字符集的大小是否仅限于小写字母k值的典型范围是否需要多次查询不同的k值10. 个人实践心得在解决这个问题时我总结了以下几点经验不要被表面现象迷惑看似滑动窗口问题实则可能需要分治从简单例子入手手动计算小例子能帮助理解问题本质考虑极端情况空串、k0、所有字符相同等情况容易忽略多种解法对比理解不同解法的时间和空间复杂度差异测试驱动开发先写测试用例再实现确保覆盖各种情况这个问题很好地展示了算法思维的重要性。有时候看似复杂的问题可以通过巧妙的分解转化为更简单的子问题。这种分治思想不仅适用于字符串处理在树形结构、排序算法等领域也有广泛应用。

LeetCode 395题解析：分治法求解最长K重复字符子串

相关推荐

Kubernetes集群筑基：etcd环境准备与生产级调优指南

GNN生产环境部署实战：从模型导出到高并发推理服务

Kubernetes集群基石：etcd分布式共识底座部署与运维实战

更多资讯

leetcode 136只出现一次的数字

YOLOv5s部署RK3588 NPU实战：INT8量化与性能调优避坑指南

SpringBoot+Vue构建高效航班进出港管理系统

智能安防转型实战：从卖设备到卖方案，AI算法与边缘计算落地指南

Knative docs 仓库 GitHub 协作工作流详解：从 Fork 到 PR 合并的全流程指南

RGB转YCbCr图像通道拆分与可视化实战指南

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？