在 LeetCode 的字符串滑窗分类里395 这题属于那种一眼看不出答案、但看透后又很爽的题目。题名非常直白至少有 K 个重复字符的最长子串。给定一个字符串s和一个整数k你需要找到一个最长连续子串让子串里每一个出现过的字符出现次数都至少是k。它不像“最长无重复子串”那样靠一个滑动窗口就顺理成章也不是简单的频率统计题——它同时考察分治思想、双指针的单调性判断、以及“枚举参数化条件”的解题套路。我第一次做的时候用暴力枚举交了三发 TLE后来静下心把两种正解都写了一遍才真正搞懂这题为什么能在热门题里被反复讨论。这篇文章就把完整的拆解、代码和踩坑记录整理出来适合正在按专题刷 LeetCode、准备面试或者单纯想练一练滑动窗口变体的朋友。1. 先看懂题目再说解法LeetCode 395 到底在考什么1.1 题目复述与“至少K个”的正确理解先花一分钟把题意抠清楚。给定一个字符串s和一个整数k返回最长子串的长度且这个子串中每个出现过的字符出现次数都必须大于等于k。注意是“子串”不是“子序列”所以要求连续也注意是“至少 K 个”不是“恰好 K 个”。举个例子s aaabb, k 3。整个串aaabb里a出现 3 次、b出现 2 次b不满足至少 3 次所以整串不行。再看子串aaa里面只有a且出现 3 次满足条件长度是 3。还有没有更长的aaab中b只有 1 次不行aabb中a和b各 2 次也不行。所以答案是 3。这个定义里有个容易忽略的点题目只关心“出现过的字符”没有出现的字符不需要管。所以一个子串只要包含的字符种类数量有限并且每种字符的频率都达到k就合法。这相当于给子串加了一个“频率下限约束”而不是常见的“连续不重复约束”或“种类上限约束”。1.2 为什么这道题能卡住一批人不少朋友拿到题后的第一反应是滑动窗口因为“最长子串”四个字太有迷惑性了。但普通双指针在这道题上会直接卡住原因是不满足单调性。什么叫单调性以“最长无重复字符子串”为例固定右端点如果当前窗口已经满足“无重复”那左端点再怎么右移窗口变小依然无重复。也就是说条件在窗口收缩方向上只可能从满足变成满足不会从满足跳成不满足这种性质支撑了双指针的移动逻辑。但 395 不一样。比如s aaabbb, k 3整个窗口满足条件a、b各 3 次此时把左指针右移一位窗口变成aabbba只有 2 次不满足了。同一个窗口在收缩过程中从满足变成了不满足单调性直接破掉。所以朴素滑动窗口在这道题上不能用这也是题目第一个真正的门槛。1.3 暴力法能得多少分如果面试官让你先给一个能跑的方案暴力枚举是可以的。枚举所有子串起点和终点统计每个字符出现次数再判断是否所有非 0 频率都不小于k。def longestSubstring(s: str, k: int) - int: n len(s) ans 0 for i in range(n): cnt [0] * 26 for j in range(i, n): cnt[ord(s[j]) - ord(a)] 1 if all(c 0 or c k for c in cnt): ans max(ans, j - i 1) return ans复杂度是O(26 * n^2)能跑过很小的数据但题目s.length可以到一万、十万级别铁定 TLE。不过暴力法也有价值它帮我们把问题模型彻底看清后续两种正解都是从“如何避免重复枚举”出发的。2. 解法一分治递归——用一个“坏字符”切开问题2.1 关键观察全局次数不足 K 的字符必须被排除这题最优雅的出发点是一个反证法观察如果某个字符c在整个字符串中出现的总次数小于k那么任何包含c的子串都不可能满足“每个字符至少 k 次”。因为整个字符串里它都不足k次任何子串里它只会更少。换句话说c是一个“坏字符”它会把字符串分隔成若干段坏字符左侧一段、右侧一段以及坏字符位置之间的所有片段。最终的答案一定不可能跨越坏字符只能完整落在某个片段内部。于是问题被切割成更短的子问题——对每个片段分别求解取最大值。这不就是天然的分治吗举个例子s abac, k 2。全局频率a出现 2 次b出现 1 次c出现 1 次。b和c都是坏字符。以b分割左边是a右边是aca长度 1 但频率 1 不满足ac里c又不足继续切掉c剩下a也不满足。最终返回 0确实找不到长度至少 2 的合法子串。2.2 递归实现的分步拆解实现分治时并不需要真的在字符串里找到每一个坏字符的位置再分别切开只需要找到“第一个坏字符”把它作为分界点递归处理左边和右边即可。因为递归过程中右侧片段里的其他坏字符会被下一层继续处理。步骤可以拆成四步统计当前字符串片段的频率。找到第一个频率大于 0 但小于k的字符记为坏字符。如果找不到任何坏字符说明当前片段本身满足要求直接返回片段长度。如果找到了以这个坏字符为分隔符把所有分割出来的片段递归求解返回最大长度。这里用 Python 的split会非常爽代码很短class Solution: def longestSubstring(self, s: str, k: int) - int: if not s: return 0 cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 bad -1 for i in range(26): if 0 cnt[i] k: bad i break if bad -1: return len(s) ch chr(ord(a) bad) return max(self.longestSubstring(part, k) for part in s.split(ch))注意这里split(ch)会去掉所有坏字符并且自动把字符串切成多段。如果某一段是空字符串递归后返回 0不影响结果。这个写法非常简洁但面试时最好说清楚思路再补一个基于索引下标的版本避免显得只会用split偷懒。2.3 复杂度分析与“看起来很美”的表象分治法的复杂度需要仔细说。每一层递归都要遍历当前片段统计频率同时遍历 26 个计数找出坏字符这部分是O(26 * n)。然后递归处理左右片段。如果分割得很均匀比如每次恰好在中间切开那么T(n) 2T(n/2) O(26n)复杂度是O(n log n)。但这是理想情况。坏字符可能出现在字符串开头导致一边长度为 0、另一边几乎全量最坏情况下每次只切掉一个字符递归深度变成O(n)总复杂度退化为O(n^2)。有的题解会写成O(26 * n)那是在“最多只能切 26 种字符”的假设下给出的乐观估计严格推导并不成立。面试里如果被追问建议老实回答最坏O(n^2)平均接近O(n log n)空间复杂度因为递归栈和切片是O(n)。2.4 分治法的边界处理细节用分治法时最容易翻车的几个点空串一定要返回 0否则max传空序列会报错。找坏字符时判断条件是0 cnt[i] k不能写成cnt[i] k否则频率为 0 的字符也会被当成坏字符递归进去全是 0什么都得不到。用split时坏字符本身被丢掉了这正好符合“包含坏字符的子串一定不合法”的结论但如果面试官要求返回子串本身而不是长度记得额外记录最优片段的下标范围。k 1时不存在坏字符直接返回整串长度这个逻辑是通顺的。3. 解法二滑动窗口 枚举字符种类数把复杂度压到 O(26×n)3.1 普通双指针失败的根因以及一个巧妙的“人造单调性”前面说过普通双指针失效的原因是不满足单调性窗口收缩时可能把某个字符的频率从k降到k-1导致窗口从不合法其实准确说是窗口从“满足条件”变成“不满足条件”。那么能不能人为制造一个单调性出来可以。给窗口加一个额外的限制窗口内字符的种类数必须恰好等于t。听起来很奇怪但正是这个限制让双指针重新可用。为什么如果固定了种类数t那么窗口扩张时字符种类数只增不减一旦超过t就必须收缩左端点收缩到种类数重新等于t就可以停下来。此时移动方向有了明确的边界规则单调性回来了。外层再把t从 1 枚举到 26覆盖所有可能的合法窗口字符种类数问题就解决了。3.2 双指针代码中三个核心计数器的维护实现这个滑动窗口需要维护三个计数器freq窗口内每个字符的出现次数。distinct窗口内出现次数大于 0 的字符种类数。ok窗口内出现次数已经达到k的字符种类数。右指针每扩展一个字符c就更新freq[c]。如果freq[c]从 0 变成 1distinct加 1如果freq[c]刚好变成kok加 1。左指针收缩时反向更新如果freq[c]从k变成k-1ok减 1如果freq[c]从 1 变成 0distinct减 1。这里有个非常容易写错的地方必须先判断旧状态再更新频率还是先更新频率再判断我建议固定成“先判断变化事件再更新频率”。比如右指针扩展时如果旧频率是 0那么distinct加 1如果旧频率是k-1那么ok加 1。左指针收缩时同理。这样逻辑最不容易出错。class Solution: def longestSubstring(self, s: str, k: int) - int: n len(s) ans 0 for t in range(1, 27): if t * k n: break freq [0] * 26 left 0 distinct 0 ok 0 for right, ch in enumerate(s): c ord(ch) - ord(a) if freq[c] 0: distinct 1 freq[c] 1 if freq[c] k: ok 1 while distinct t: c2 ord(s[left]) - ord(a) if freq[c2] k: ok - 1 freq[c2] - 1 if freq[c2] 0: distinct - 1 left 1 if distinct t and ok t: ans max(ans, right - left 1) return ans注意更新答案的条件是distinct t and ok t不是distinct t。因为窗口必须“恰好”包含t种字符且这t种全部达标才能保证每个字符都满足至少k次。如果只是distinct t可能窗口里字符种类不足但有些字符频率不达标此时并不是一个合法候选。3.3 剪枝不是每种 t 都值得枚举外层循环本来可以从 1 到 26看起来固定 26 次循环也不大。但加一个剪枝能让代码更聪明如果t * k n那么不可能存在一个窗口包含t种字符并且每种至少k次因为最小长度就是t * k。所以直接break退出循环。这个剪枝在k很大的时候效果明显。比如k 10000而n只有 1000那么第一次循环1 * k n成立直接退出一行不跑返回 0。代码效率瞬间拉满。3.4 复杂度与正确性思路固定t时双指针整体只遍历一次字符串复杂度O(n)。外层最多 26 次总共O(26n)空间O(26)。这是这道题的稳定最优复杂度不会像分治法那样有最坏退化。正确性可以从这个角度理解任何满足条件的合法子串一定恰好有某种字符种类数t*并且t*在 1 到 26 之间。当外层循环枚举到t t*时双指针扫描的所有窗口中一定有一个窗口恰好覆盖这个合法子串。覆盖的过程中如果扩右端点时混入了多余种类窗口会自动收缩左端点把多余字符清出去最终在某一步更新答案。正因为枚举了所有种类数所以不会漏掉任何一种可能性。3.5 普通滑动窗口与“枚举种类数滑动窗口”的区别很多初学者把两者混在一起。做一个对比场景窗口条件能否直接用双指针为什么最长无重复子串窗口内无重复字符能收缩窗口会让条件保持满足395 不固定种类数窗口内每个字符频率 ≥ k不能收缩窗口可能使某个字符频率低于 k395 固定种类数 t窗口内恰好 t 种且每种 ≥ k能种类数超过 t 时强制收缩方向明确这个对比在面试里非常有用可以说清楚“为什么枚举 t 是关键”。4. 用测试用例把两个解法按在地上摩擦K 的参数敏感性4.1 一列用例眼见为实自己写代码的时候不能只跑一个示例就收工。下面这些用例覆盖了常见的边界情况两个解法都应该能通过输入k期望输出说明aaabb33只有aaa合法ababbc25ababb中 a 2 次、b 3 次aabbb33整个串 a 只有 2 次只有bbb合法abcabc26整个串 a、b、c 各 2 次abcd20每种字符只出现 1 次aaabbb36整个串 a、b 各 3 次50空串没有合法子串a11单字符出现 1 次满足a20单字符频率不够跑这些用例时重点是看两个解法返回是否一致。只要有一个不一致就要立刻回去检查实现。4.2 为什么 k 值直接决定题目难度k是这道题的灵魂参数和热搜词里经常出现的“k 值选择”是同一个道理——算法结果对 k 高度敏感。当k 1时问题突然变简单任何子串里的字符都至少出现 1 次所以整个字符串本身一定合法直接返回len(s)即可。当k 2时条件变成“每种字符至少成对出现”答案通常是把那些单独出现一次的字符切掉后的某个片段。当k很大比如大于字符串长度的一半时可能根本不存在合法子串答案直接是 0。有意思的是如果面试官追问k 0怎么办要注意从数学定义上讲要求每个字符出现次数至少为 0 是恒真的所以整个字符串一定合法答案就是n。但滑动窗口代码里freq[c] k这个判断会变成freq[c] 0逻辑会乱所以需要单独在函数开头判断处理。LeetCode 的约束里k 1不需要管但面试时能说一句“如果 k 等于 0我直接在入口返回 n”会显得你考虑得周全。4.3 分治与滑窗在同一用例下的行为对比还有一种很有意思的对比在某些极端用例下分治法和滑动窗口的表现完全不同。比如s aaaaaaaa, k 3。分治法发现a频率 8 大于等于 3没有坏字符直接返回 8。滑动窗口枚举t外层t 1时窗口内distinct 1, ok 1更新答案是 8t 2时左推右也凑不出两种字符所以答案是 0最终返回 8。两个解法结果一致。再看s ababab, k 2。分治法发现a、b都满足 2 次以上直接返回 6。滑动窗口枚举t 2时窗口可以覆盖全串distinct 2, ok 2答案 6。两者也都对。这说明在“全字符串本身合法”的场景里分治法很直接而滑动窗口需要多跑几次外层循环才收敛。反过来在“坏字符很多”的场景里分治可能递归很深滑动窗口依然稳定线性。5. C/Python 多语言实现及易错点精讲5.1 Python 滑动窗口完整代码前面已经给了 Python 的滑动窗口实现。这里再给一个完整的、带清晰注释的版本方便直接复制到本地跑class Solution: def longestSubstring(self, s: str, k: int) - int: n len(s) if n 0 or k 0: return n ans 0 # 枚举窗口内允许出现的字符种类数 t for t in range(1, 27): if t * k n: break freq [0] * 26 left 0 distinct 0 ok 0 for right in range(n): c ord(s[right]) - ord(a) # 右指针进入窗口 if freq[c] 0: distinct 1 freq[c] 1 if freq[c] k: ok 1 # 种类数超限收缩左指针 while distinct t: c2 ord(s[left]) - ord(a) if freq[c2] k: ok - 1 freq[c2] - 1 if freq[c2] 0: distinct - 1 left 1 # 恰好 t 种且 t 种全部达标 if distinct t and ok t: ans max(ans, right - left 1) return ans这段代码用了整型索引而不是enumerate字符串逻辑上和之前一致。个人建议把缩进和变量名写清楚因为面试写白板时最怕这种多计数器更新。5.2 C 滑动窗口代码如果需要写 C 版本数组代替列表思路完全一样class Solution { public: int longestSubstring(string s, int k) { int n s.size(); if (n 0 || k 0) return n; int ans 0; for (int t 1; t 26; t) { if (t * k n) break; vectorint freq(26, 0); int left 0, distinct 0, ok 0; for (int right 0; right n; right) { int c s[right] - a; if (freq[c] 0) distinct; freq[c]; if (freq[c] k) ok; while (distinct t) { int c2 s[left] - a; if (freq[c2] k) --ok; --freq[c2]; if (freq[c2] 0) --distinct; left; } if (distinct t ok t) { ans max(ans, right - left 1); } } } return ans; } };注意 C 里string的字符减法要保证字符是小写字母题目已经是这个约束。如果扩展成 ASCII 可见字符就把数组长度改成 128外层循环上限也改成 128其他逻辑不变。5.3 容易让代码“莫名其妙的 WA”的三个点我刷这题时踩过几个坑每次都是样例过了但提交 WA最后才发现问题。第一个坑是ok的更新时机。很多人喜欢把频率更新完再判断freq[c] k这样做在右指针扩展时问题不大但左指针收缩时会出问题。比如freq[c]从k变成k-1更新后再判断freq[c] k已经是 false你可能忘了在频率变化瞬间把ok减下去。所以最安全的写法就是在freq[c]变化前后分别判断一次或者严格用“旧频率决定事件”的写法。第二个坑是窗口收缩条件。while distinct t这里必须是不能是。如果用那么恰好distinct t时也会进入收缩把合法窗口拆掉最后答案永远偏小。类似的“边界差一错误”在滑动窗口里很常见。第三个坑是不剪枝就超时。虽然26是个常数但在极端大n下O(26n)完全够用超时大概率是别的写法问题。不过如果你把外层循环写成range(1, len(s) 1)那就彻底废了复杂度直接变成O(n^2)。所以一定要记住枚举t是枚举字符种类数不是枚举子串长度。6. 面试官视角这道题怎么答才能拿高分6.1 从“背题”到“讲题”答题节奏建议如果你在面试中遇到 395不建议上来就甩滑动窗口代码。面试官想看的是你的思考链路而不是背题能力。我建议按这个节奏走先说清楚题意举一个例子验证理解。给一个最简单的暴力解说明复杂度是 O(n²)。抛出关键观察某个字符全局频率小于 k它就是坏字符于是可以分治。给出分治解法并分析最坏复杂度。如果时间充裕主动提出能不能做到稳定的 O(n)。然后引导到固定字符种类数的滑动窗口想法先讲为什么普通双指针失效再讲如何通过枚举 t 恢复单调性最后写代码。这样整个过程非常自然面试官也能看到你从不可能到可能的思考过程。反过来如果你一上来就背滑窗代码一旦面试官追问“为什么直接滑窗不行”你可能会愣住。6.2 延伸题同一个 K不同题目里的含义完全不同刷题多了你会发现很多题都带一个k但含义完全不同特别容易造成思维惯性。第 340 题Longest Substring with At Most K Distinct Characters。这里的K是“最多允许的字符种类数”窗口条件是在种类数不超过 K 的前提下尽量长。第 424 题Longest Repeating Character Replacement。这里的K是“最多可以替换的字符数”窗口条件是“最多出现次数 K 窗口长度”。第 395 题这里的K是“每个字符最少出现次数”相当于一个频率下限。第 76 题Minimum Window Substring里的 K 其实是目标串里每个字符的需求频率不是单一参数。这些题都叫滑动窗口但窗口的合法性判断方向几乎都不一样。如果你把 395 的条件套到 340 上代码一定不对。所以刷题总结时比起背模板更重要的是记住每个模板背后的条件模型。395 的核心模型就是“枚举种类数 频率下限”这个模型在面试里复现率很高。6.3 复盘把 395 的思路迁移到真实业务最后说点题外话。这种“频率下限 最长连续片段”的模型不只在刷题里存在。比如日志分析中要找出连续一段时间内每个错误码都至少出现 K 次的窗口或者电商场景下要找出一个连续时间段让每个热门商品都被至少浏览 K 次的区间。这些都是 395 的变体。这时候参数K的选择就很讲究了。K 设得太小窗口会无限接近整个序列没区分度K 设得太大窗口长度又会被压得很短可能找不到合法区间。就像热搜词里总有人讨论“k 值选择”一样很多算法问题最后都在调这个参数395 也不例外。刷题时对k多点敏感度以后做真实数据分析时也能多想一层不算白费。我自己刷这题时第一次被分治的“切断坏字符”思路惊艳到后来又写了滑动窗口才慢慢发现滑窗的稳定复杂度在真实场景里更实用。如果你也是初次接触这题建议把两种解法都实现一遍再跑到本地跑一遍上面那几个用例。等你能三分钟讲清“为什么普通双指针失效、为什么要枚举 t、什么时候 ok 要加减”这三个点这题就真正吃透了。 LeetCode 395：至少有K个重复字符的最长子串（分治+滑窗）
在 LeetCode 的字符串滑窗分类里395 这题属于那种一眼看不出答案、但看透后又很爽的题目。题名非常直白至少有 K 个重复字符的最长子串。给定一个字符串s和一个整数k你需要找到一个最长连续子串让子串里每一个出现过的字符出现次数都至少是k。它不像“最长无重复子串”那样靠一个滑动窗口就顺理成章也不是简单的频率统计题——它同时考察分治思想、双指针的单调性判断、以及“枚举参数化条件”的解题套路。我第一次做的时候用暴力枚举交了三发 TLE后来静下心把两种正解都写了一遍才真正搞懂这题为什么能在热门题里被反复讨论。这篇文章就把完整的拆解、代码和踩坑记录整理出来适合正在按专题刷 LeetCode、准备面试或者单纯想练一练滑动窗口变体的朋友。1. 先看懂题目再说解法LeetCode 395 到底在考什么1.1 题目复述与“至少K个”的正确理解先花一分钟把题意抠清楚。给定一个字符串s和一个整数k返回最长子串的长度且这个子串中每个出现过的字符出现次数都必须大于等于k。注意是“子串”不是“子序列”所以要求连续也注意是“至少 K 个”不是“恰好 K 个”。举个例子s aaabb, k 3。整个串aaabb里a出现 3 次、b出现 2 次b不满足至少 3 次所以整串不行。再看子串aaa里面只有a且出现 3 次满足条件长度是 3。还有没有更长的aaab中b只有 1 次不行aabb中a和b各 2 次也不行。所以答案是 3。这个定义里有个容易忽略的点题目只关心“出现过的字符”没有出现的字符不需要管。所以一个子串只要包含的字符种类数量有限并且每种字符的频率都达到k就合法。这相当于给子串加了一个“频率下限约束”而不是常见的“连续不重复约束”或“种类上限约束”。1.2 为什么这道题能卡住一批人不少朋友拿到题后的第一反应是滑动窗口因为“最长子串”四个字太有迷惑性了。但普通双指针在这道题上会直接卡住原因是不满足单调性。什么叫单调性以“最长无重复字符子串”为例固定右端点如果当前窗口已经满足“无重复”那左端点再怎么右移窗口变小依然无重复。也就是说条件在窗口收缩方向上只可能从满足变成满足不会从满足跳成不满足这种性质支撑了双指针的移动逻辑。但 395 不一样。比如s aaabbb, k 3整个窗口满足条件a、b各 3 次此时把左指针右移一位窗口变成aabbba只有 2 次不满足了。同一个窗口在收缩过程中从满足变成了不满足单调性直接破掉。所以朴素滑动窗口在这道题上不能用这也是题目第一个真正的门槛。1.3 暴力法能得多少分如果面试官让你先给一个能跑的方案暴力枚举是可以的。枚举所有子串起点和终点统计每个字符出现次数再判断是否所有非 0 频率都不小于k。def longestSubstring(s: str, k: int) - int: n len(s) ans 0 for i in range(n): cnt [0] * 26 for j in range(i, n): cnt[ord(s[j]) - ord(a)] 1 if all(c 0 or c k for c in cnt): ans max(ans, j - i 1) return ans复杂度是O(26 * n^2)能跑过很小的数据但题目s.length可以到一万、十万级别铁定 TLE。不过暴力法也有价值它帮我们把问题模型彻底看清后续两种正解都是从“如何避免重复枚举”出发的。2. 解法一分治递归——用一个“坏字符”切开问题2.1 关键观察全局次数不足 K 的字符必须被排除这题最优雅的出发点是一个反证法观察如果某个字符c在整个字符串中出现的总次数小于k那么任何包含c的子串都不可能满足“每个字符至少 k 次”。因为整个字符串里它都不足k次任何子串里它只会更少。换句话说c是一个“坏字符”它会把字符串分隔成若干段坏字符左侧一段、右侧一段以及坏字符位置之间的所有片段。最终的答案一定不可能跨越坏字符只能完整落在某个片段内部。于是问题被切割成更短的子问题——对每个片段分别求解取最大值。这不就是天然的分治吗举个例子s abac, k 2。全局频率a出现 2 次b出现 1 次c出现 1 次。b和c都是坏字符。以b分割左边是a右边是aca长度 1 但频率 1 不满足ac里c又不足继续切掉c剩下a也不满足。最终返回 0确实找不到长度至少 2 的合法子串。2.2 递归实现的分步拆解实现分治时并不需要真的在字符串里找到每一个坏字符的位置再分别切开只需要找到“第一个坏字符”把它作为分界点递归处理左边和右边即可。因为递归过程中右侧片段里的其他坏字符会被下一层继续处理。步骤可以拆成四步统计当前字符串片段的频率。找到第一个频率大于 0 但小于k的字符记为坏字符。如果找不到任何坏字符说明当前片段本身满足要求直接返回片段长度。如果找到了以这个坏字符为分隔符把所有分割出来的片段递归求解返回最大长度。这里用 Python 的split会非常爽代码很短class Solution: def longestSubstring(self, s: str, k: int) - int: if not s: return 0 cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 bad -1 for i in range(26): if 0 cnt[i] k: bad i break if bad -1: return len(s) ch chr(ord(a) bad) return max(self.longestSubstring(part, k) for part in s.split(ch))注意这里split(ch)会去掉所有坏字符并且自动把字符串切成多段。如果某一段是空字符串递归后返回 0不影响结果。这个写法非常简洁但面试时最好说清楚思路再补一个基于索引下标的版本避免显得只会用split偷懒。2.3 复杂度分析与“看起来很美”的表象分治法的复杂度需要仔细说。每一层递归都要遍历当前片段统计频率同时遍历 26 个计数找出坏字符这部分是O(26 * n)。然后递归处理左右片段。如果分割得很均匀比如每次恰好在中间切开那么T(n) 2T(n/2) O(26n)复杂度是O(n log n)。但这是理想情况。坏字符可能出现在字符串开头导致一边长度为 0、另一边几乎全量最坏情况下每次只切掉一个字符递归深度变成O(n)总复杂度退化为O(n^2)。有的题解会写成O(26 * n)那是在“最多只能切 26 种字符”的假设下给出的乐观估计严格推导并不成立。面试里如果被追问建议老实回答最坏O(n^2)平均接近O(n log n)空间复杂度因为递归栈和切片是O(n)。2.4 分治法的边界处理细节用分治法时最容易翻车的几个点空串一定要返回 0否则max传空序列会报错。找坏字符时判断条件是0 cnt[i] k不能写成cnt[i] k否则频率为 0 的字符也会被当成坏字符递归进去全是 0什么都得不到。用split时坏字符本身被丢掉了这正好符合“包含坏字符的子串一定不合法”的结论但如果面试官要求返回子串本身而不是长度记得额外记录最优片段的下标范围。k 1时不存在坏字符直接返回整串长度这个逻辑是通顺的。3. 解法二滑动窗口 枚举字符种类数把复杂度压到 O(26×n)3.1 普通双指针失败的根因以及一个巧妙的“人造单调性”前面说过普通双指针失效的原因是不满足单调性窗口收缩时可能把某个字符的频率从k降到k-1导致窗口从不合法其实准确说是窗口从“满足条件”变成“不满足条件”。那么能不能人为制造一个单调性出来可以。给窗口加一个额外的限制窗口内字符的种类数必须恰好等于t。听起来很奇怪但正是这个限制让双指针重新可用。为什么如果固定了种类数t那么窗口扩张时字符种类数只增不减一旦超过t就必须收缩左端点收缩到种类数重新等于t就可以停下来。此时移动方向有了明确的边界规则单调性回来了。外层再把t从 1 枚举到 26覆盖所有可能的合法窗口字符种类数问题就解决了。3.2 双指针代码中三个核心计数器的维护实现这个滑动窗口需要维护三个计数器freq窗口内每个字符的出现次数。distinct窗口内出现次数大于 0 的字符种类数。ok窗口内出现次数已经达到k的字符种类数。右指针每扩展一个字符c就更新freq[c]。如果freq[c]从 0 变成 1distinct加 1如果freq[c]刚好变成kok加 1。左指针收缩时反向更新如果freq[c]从k变成k-1ok减 1如果freq[c]从 1 变成 0distinct减 1。这里有个非常容易写错的地方必须先判断旧状态再更新频率还是先更新频率再判断我建议固定成“先判断变化事件再更新频率”。比如右指针扩展时如果旧频率是 0那么distinct加 1如果旧频率是k-1那么ok加 1。左指针收缩时同理。这样逻辑最不容易出错。class Solution: def longestSubstring(self, s: str, k: int) - int: n len(s) ans 0 for t in range(1, 27): if t * k n: break freq [0] * 26 left 0 distinct 0 ok 0 for right, ch in enumerate(s): c ord(ch) - ord(a) if freq[c] 0: distinct 1 freq[c] 1 if freq[c] k: ok 1 while distinct t: c2 ord(s[left]) - ord(a) if freq[c2] k: ok - 1 freq[c2] - 1 if freq[c2] 0: distinct - 1 left 1 if distinct t and ok t: ans max(ans, right - left 1) return ans注意更新答案的条件是distinct t and ok t不是distinct t。因为窗口必须“恰好”包含t种字符且这t种全部达标才能保证每个字符都满足至少k次。如果只是distinct t可能窗口里字符种类不足但有些字符频率不达标此时并不是一个合法候选。3.3 剪枝不是每种 t 都值得枚举外层循环本来可以从 1 到 26看起来固定 26 次循环也不大。但加一个剪枝能让代码更聪明如果t * k n那么不可能存在一个窗口包含t种字符并且每种至少k次因为最小长度就是t * k。所以直接break退出循环。这个剪枝在k很大的时候效果明显。比如k 10000而n只有 1000那么第一次循环1 * k n成立直接退出一行不跑返回 0。代码效率瞬间拉满。3.4 复杂度与正确性思路固定t时双指针整体只遍历一次字符串复杂度O(n)。外层最多 26 次总共O(26n)空间O(26)。这是这道题的稳定最优复杂度不会像分治法那样有最坏退化。正确性可以从这个角度理解任何满足条件的合法子串一定恰好有某种字符种类数t*并且t*在 1 到 26 之间。当外层循环枚举到t t*时双指针扫描的所有窗口中一定有一个窗口恰好覆盖这个合法子串。覆盖的过程中如果扩右端点时混入了多余种类窗口会自动收缩左端点把多余字符清出去最终在某一步更新答案。正因为枚举了所有种类数所以不会漏掉任何一种可能性。3.5 普通滑动窗口与“枚举种类数滑动窗口”的区别很多初学者把两者混在一起。做一个对比场景窗口条件能否直接用双指针为什么最长无重复子串窗口内无重复字符能收缩窗口会让条件保持满足395 不固定种类数窗口内每个字符频率 ≥ k不能收缩窗口可能使某个字符频率低于 k395 固定种类数 t窗口内恰好 t 种且每种 ≥ k能种类数超过 t 时强制收缩方向明确这个对比在面试里非常有用可以说清楚“为什么枚举 t 是关键”。4. 用测试用例把两个解法按在地上摩擦K 的参数敏感性4.1 一列用例眼见为实自己写代码的时候不能只跑一个示例就收工。下面这些用例覆盖了常见的边界情况两个解法都应该能通过输入k期望输出说明aaabb33只有aaa合法ababbc25ababb中 a 2 次、b 3 次aabbb33整个串 a 只有 2 次只有bbb合法abcabc26整个串 a、b、c 各 2 次abcd20每种字符只出现 1 次aaabbb36整个串 a、b 各 3 次50空串没有合法子串a11单字符出现 1 次满足a20单字符频率不够跑这些用例时重点是看两个解法返回是否一致。只要有一个不一致就要立刻回去检查实现。4.2 为什么 k 值直接决定题目难度k是这道题的灵魂参数和热搜词里经常出现的“k 值选择”是同一个道理——算法结果对 k 高度敏感。当k 1时问题突然变简单任何子串里的字符都至少出现 1 次所以整个字符串本身一定合法直接返回len(s)即可。当k 2时条件变成“每种字符至少成对出现”答案通常是把那些单独出现一次的字符切掉后的某个片段。当k很大比如大于字符串长度的一半时可能根本不存在合法子串答案直接是 0。有意思的是如果面试官追问k 0怎么办要注意从数学定义上讲要求每个字符出现次数至少为 0 是恒真的所以整个字符串一定合法答案就是n。但滑动窗口代码里freq[c] k这个判断会变成freq[c] 0逻辑会乱所以需要单独在函数开头判断处理。LeetCode 的约束里k 1不需要管但面试时能说一句“如果 k 等于 0我直接在入口返回 n”会显得你考虑得周全。4.3 分治与滑窗在同一用例下的行为对比还有一种很有意思的对比在某些极端用例下分治法和滑动窗口的表现完全不同。比如s aaaaaaaa, k 3。分治法发现a频率 8 大于等于 3没有坏字符直接返回 8。滑动窗口枚举t外层t 1时窗口内distinct 1, ok 1更新答案是 8t 2时左推右也凑不出两种字符所以答案是 0最终返回 8。两个解法结果一致。再看s ababab, k 2。分治法发现a、b都满足 2 次以上直接返回 6。滑动窗口枚举t 2时窗口可以覆盖全串distinct 2, ok 2答案 6。两者也都对。这说明在“全字符串本身合法”的场景里分治法很直接而滑动窗口需要多跑几次外层循环才收敛。反过来在“坏字符很多”的场景里分治可能递归很深滑动窗口依然稳定线性。5. C/Python 多语言实现及易错点精讲5.1 Python 滑动窗口完整代码前面已经给了 Python 的滑动窗口实现。这里再给一个完整的、带清晰注释的版本方便直接复制到本地跑class Solution: def longestSubstring(self, s: str, k: int) - int: n len(s) if n 0 or k 0: return n ans 0 # 枚举窗口内允许出现的字符种类数 t for t in range(1, 27): if t * k n: break freq [0] * 26 left 0 distinct 0 ok 0 for right in range(n): c ord(s[right]) - ord(a) # 右指针进入窗口 if freq[c] 0: distinct 1 freq[c] 1 if freq[c] k: ok 1 # 种类数超限收缩左指针 while distinct t: c2 ord(s[left]) - ord(a) if freq[c2] k: ok - 1 freq[c2] - 1 if freq[c2] 0: distinct - 1 left 1 # 恰好 t 种且 t 种全部达标 if distinct t and ok t: ans max(ans, right - left 1) return ans这段代码用了整型索引而不是enumerate字符串逻辑上和之前一致。个人建议把缩进和变量名写清楚因为面试写白板时最怕这种多计数器更新。5.2 C 滑动窗口代码如果需要写 C 版本数组代替列表思路完全一样class Solution { public: int longestSubstring(string s, int k) { int n s.size(); if (n 0 || k 0) return n; int ans 0; for (int t 1; t 26; t) { if (t * k n) break; vectorint freq(26, 0); int left 0, distinct 0, ok 0; for (int right 0; right n; right) { int c s[right] - a; if (freq[c] 0) distinct; freq[c]; if (freq[c] k) ok; while (distinct t) { int c2 s[left] - a; if (freq[c2] k) --ok; --freq[c2]; if (freq[c2] 0) --distinct; left; } if (distinct t ok t) { ans max(ans, right - left 1); } } } return ans; } };注意 C 里string的字符减法要保证字符是小写字母题目已经是这个约束。如果扩展成 ASCII 可见字符就把数组长度改成 128外层循环上限也改成 128其他逻辑不变。5.3 容易让代码“莫名其妙的 WA”的三个点我刷这题时踩过几个坑每次都是样例过了但提交 WA最后才发现问题。第一个坑是ok的更新时机。很多人喜欢把频率更新完再判断freq[c] k这样做在右指针扩展时问题不大但左指针收缩时会出问题。比如freq[c]从k变成k-1更新后再判断freq[c] k已经是 false你可能忘了在频率变化瞬间把ok减下去。所以最安全的写法就是在freq[c]变化前后分别判断一次或者严格用“旧频率决定事件”的写法。第二个坑是窗口收缩条件。while distinct t这里必须是不能是。如果用那么恰好distinct t时也会进入收缩把合法窗口拆掉最后答案永远偏小。类似的“边界差一错误”在滑动窗口里很常见。第三个坑是不剪枝就超时。虽然26是个常数但在极端大n下O(26n)完全够用超时大概率是别的写法问题。不过如果你把外层循环写成range(1, len(s) 1)那就彻底废了复杂度直接变成O(n^2)。所以一定要记住枚举t是枚举字符种类数不是枚举子串长度。6. 面试官视角这道题怎么答才能拿高分6.1 从“背题”到“讲题”答题节奏建议如果你在面试中遇到 395不建议上来就甩滑动窗口代码。面试官想看的是你的思考链路而不是背题能力。我建议按这个节奏走先说清楚题意举一个例子验证理解。给一个最简单的暴力解说明复杂度是 O(n²)。抛出关键观察某个字符全局频率小于 k它就是坏字符于是可以分治。给出分治解法并分析最坏复杂度。如果时间充裕主动提出能不能做到稳定的 O(n)。然后引导到固定字符种类数的滑动窗口想法先讲为什么普通双指针失效再讲如何通过枚举 t 恢复单调性最后写代码。这样整个过程非常自然面试官也能看到你从不可能到可能的思考过程。反过来如果你一上来就背滑窗代码一旦面试官追问“为什么直接滑窗不行”你可能会愣住。6.2 延伸题同一个 K不同题目里的含义完全不同刷题多了你会发现很多题都带一个k但含义完全不同特别容易造成思维惯性。第 340 题Longest Substring with At Most K Distinct Characters。这里的K是“最多允许的字符种类数”窗口条件是在种类数不超过 K 的前提下尽量长。第 424 题Longest Repeating Character Replacement。这里的K是“最多可以替换的字符数”窗口条件是“最多出现次数 K 窗口长度”。第 395 题这里的K是“每个字符最少出现次数”相当于一个频率下限。第 76 题Minimum Window Substring里的 K 其实是目标串里每个字符的需求频率不是单一参数。这些题都叫滑动窗口但窗口的合法性判断方向几乎都不一样。如果你把 395 的条件套到 340 上代码一定不对。所以刷题总结时比起背模板更重要的是记住每个模板背后的条件模型。395 的核心模型就是“枚举种类数 频率下限”这个模型在面试里复现率很高。6.3 复盘把 395 的思路迁移到真实业务最后说点题外话。这种“频率下限 最长连续片段”的模型不只在刷题里存在。比如日志分析中要找出连续一段时间内每个错误码都至少出现 K 次的窗口或者电商场景下要找出一个连续时间段让每个热门商品都被至少浏览 K 次的区间。这些都是 395 的变体。这时候参数K的选择就很讲究了。K 设得太小窗口会无限接近整个序列没区分度K 设得太大窗口长度又会被压得很短可能找不到合法区间。就像热搜词里总有人讨论“k 值选择”一样很多算法问题最后都在调这个参数395 也不例外。刷题时对k多点敏感度以后做真实数据分析时也能多想一层不算白费。我自己刷这题时第一次被分治的“切断坏字符”思路惊艳到后来又写了滑动窗口才慢慢发现滑窗的稳定复杂度在真实场景里更实用。如果你也是初次接触这题建议把两种解法都实现一遍再跑到本地跑一遍上面那几个用例。等你能三分钟讲清“为什么普通双指针失效、为什么要枚举 t、什么时候 ok 要加减”这三个点这题就真正吃透了。