1. 题目到底在问什么拆解题意与核心难点1.1 先读懂题一个带着最少出现次数要求的最长区间问题LeetCode 395这道题题面很短但第一次接触的人很容易理解偏。原题描述是这样的给你一个字符串s和一个整数k请你找出s中的最长子串要求该子串中的每一个字符出现次数都不少于k。先抠字眼。子串意味着必须是连续的不是子序列所以排序、重新排列这类操作想都不用想。每一个字符指的是子串里真实出现的字符不是整个字符串里的所有字符。也就是说子串里出现的每种字母次数都要大于等于k。举个例子s aaabbk 3。整个字符串里a出现 3 次b出现 2 次。如果选整个字符串b只有 2 次小于 3不满足。那只能选aaa长度是 3这就是答案。再比如s ababbck 2。整个字符串里c只出现 1 次不满足去掉它剩下的ababb中a出现 2 次、b出现 3 次满足条件长度是 5。这类题目的本质是在一个字符串里找一个最长的连续区间使区间内的字符频率分布满足一个全局约束。你可以把它理解为带条件的最大窗口问题但这个条件不是加减法能直接判断的而是对窗口内所有字符做一次频率体检。1.2 为什么这题不是简单的滑动窗口刷过滑动窗口专题的人看到最长子串四个字第一反应就是双指针。但你要是直接套标准滑动窗口模板很快会发现不对劲。标准滑动窗口能工作的前提是窗口扩展和收缩时我们能明确判断当前窗口是否合法以及该不该移动左指针。比如 LeetCode 3 无重复字符的最长子串窗口是否合法取决于有没有重复字符右指针每走一步左指针可以跟着移动条件清晰。LeetCode 76 最小覆盖子串窗口是否合法取决于是否覆盖了目标字符集也是一个容易判断的布尔条件。但这题不一样。窗口的合法性取决于每种字符出现次数是否都大于等于 k而且这个约束没有明确的目标值可以比对。你想判断窗口合法至少需要知道窗口里有哪几种字符、每种出现几次、有没有低于 k 的。更麻烦的是一旦左指针收缩某个字符次数被减到 k 以下这个窗口立刻非法但你不知道到底该收缩到哪一步才算完。你可能会想那就让右指针一直走左指针在窗口不合法时收缩直到重新合法。问题来了什么时候算不合法比如k 3窗口里a有 2 次、b有 5 次这算不合法吧但收缩左指针应该删掉哪个字符删掉一个aa变成 1 次更不合法删掉一个bb变成 4 次窗口还是不合法。你没有一个明确的合法目标左指针的移动就失去了方向。所以这道题真正的难点不在滑动窗口本身而在于如何设计一个可控的窗口约束条件。理解了这一点后面的分治法和固定字符种类数滑动窗口解法你才能看出它们各自的设计动机。2. 解法一分治法——把大问题切到不能再切2.1 分治的核心思想找到一个坏字符分治法解决这题的切入点非常朴素如果一个字符在某个区间里出现的总次数小于 k那么任何包含这个字符的子串都不可能满足条件因为只要包含它它的出现次数就不可能高于它在整个区间里的次数。换句话讲这个坏字符就是天然的切割点。所有满足条件的子串一定分布在坏字符的左半边或右半边绝对不可能横跨它。于是问题被拆成了两个更小的子问题递归处理即可。看一下具体例子s abcabcabck 3。每个字符都出现了 3 次正好等于 k整个字符串就是答案长度 9。但如果s abcabcabk 3c只出现了 2 次小于 3那么任何包含c的子串都不行答案只能从被c切割出的若干段里找。按c切分后剩下的两段分别是ab和ab长度都只有 2小于 k直接返回 0。最终答案就是 0因为没有子串满足每个字符都出现至少 3 次。这个思路还有个可选的剪枝条件如果当前处理的区间长度本身就小于 k那无论如何都不可能满足条件直接返回 0。因为哪怕整个区间只有一种字符它也最多出现len次小于 k不满足要求。2.2 递归实现从统计频率到切割重组的完整流程我直接给出 Java 实现然后逐段拆解。class Solution { public int longestSubstring(String s, int k) { return dfs(s, 0, s.length() - 1, k); } private int dfs(String s, int left, int right, int k) { // 区间长度小于 k不可能满足条件 if (right - left 1 k) { return 0; } // 统计当前区间内每个字符的出现次数 int[] count new int[26]; for (int i left; i right; i) { count[s.charAt(i) - a]; } // 找出一个出现次数大于 0 但小于 k 的坏字符 char split 0; boolean valid true; for (int i 0; i 26; i) { if (count[i] 0 count[i] k) { split (char) (i a); valid false; break; } } // 如果当前区间所有字符出现次数都大于等于 k直接返回整个区间长度 if (valid) { return right - left 1; } // 以坏字符为分割点递归处理每一段 int i left; int result 0; while (i right) { // 跳过连续的坏字符 while (i right s.charAt(i) split) { i; } if (i right) { break; } int start i; // 找到这段的右边界遇到下一个坏字符为止 while (i right s.charAt(i) ! split) { i; } result Math.max(result, dfs(s, start, i - 1, k)); } return result; } }流程拆开是这样的第一步统计区间内每个字符的出现次数。这里用一个长度为 26 的数组因为题目默认字符串只包含小写字母。第二步扫描统计结果找到第一个出现次数大于 0 且小于 k 的字符。为什么是第一个因为只需要一个切割点。只要存在一个坏字符整个区间就不可能直接满足条件必须切分。选哪一个都行后续递归会处理其他坏字符。第三步如果扫描完发现所有出现过的字符次数都大于等于 k说明当前区间本身就是一个合法候选直接返回区间长度。第四步切割。从left到right扫一遍遇到坏字符就跳过把中间被分隔开的每一段递归处理取各段结果的最大值。这里有个很容易写错的点切割时不能简单地在坏字符的位置二分因为坏字符可能出现多次。你要做的是把区间按坏字符的所有出现位置切成若干段每一段单独递归。我的实现里用了一个嵌套 while 循环来定位每段的起止位置核心思路是找到一个非坏字符的位置作为起点向后扩展直到遇到坏字符或越界然后递归处理这一段。2.3 分治的复杂度与适用边界分治法的时间复杂度最坏情况下是 O(n^2)最好情况是 O(n)。为什么会有这么宽的波动关键取决于每次递归找到的坏字符能把区间切得多均匀。最坏的情况是每次切分只排除一个字符剩下的区间几乎没变小递归深度只有 26 层因为字符集只有 26 个字母每层至少排除一种字符但每一层的总扫描长度接近 n所以总体是 26 乘以 n 的量级。如果切分很均匀递归深度变成对数级别每一层总扫描长度还是 n复杂度接近 O(n log n)。很多资料说分治法最坏 O(n^2)其实在字符集大小固定为 26 的情况下最坏其实是 O(26n)也就是 O(n)。因为每次递归必然至少有一种字符被排除递归深度不可能超过字符集大小。这个细节面试时主动说出来面试官会认为你真的理解了这个算法的边界。空间复杂度方面递归栈深度最多 26加上每次递归创建长度为 26 的计数数组空间是 O(26) 常数级可以认为是 O(1)。分治法的优势是思路自然、代码直观适合在面试中作为第一个解答说出来。劣势是想证明复杂度时有点绕而且代码里切割逻辑如果写不熟练容易出 bug。我建议把分治作为保底方案真正想展示功底还是得看下一节的滑动窗口解法。3. 解法二滑动窗口 枚举字符种类数——面试官最想看到的答案3.1 标准滑动窗口失效的根源恰恰是解法的突破口前文说了标准滑动窗口失效是因为窗口的合法性条件没有明确的收缩目标。但如果换个思路窗口内出现的字符种类数是可以被固定的。设想一下如果我能控制窗口内恰好只允许出现t种字符在这个前提下找每种字符出现次数都大于等于 k的最长子串问题是不是就变得可解了因为t被固定后窗口的约束条件就完整了右指针扩展时如果窗口内字符种类数超过t左指针就得收缩直到种类数回到t以内。这就有了明确的收缩条件。而字符集只有 26 个小写字母t的取值范围是 1 到 26直接枚举所有t对每个t跑一次标准的滑动窗口全局最大值就是答案。这个思路第一次看到的人都会觉得这也能行但仔细想一下它是完全正确的。最优解对应的子串它的字符种类数一定是 1 到 26 中的某个整数。当我们枚举到那个整数时滑动窗口在遍历过程中一定能捕捉到该子串或者至少捕捉到一个不短于它的合法子串。所以最终答案不会漏。复杂度是多少每次滑动窗口是 O(n)枚举 26 次总复杂度 O(26n) O(n)。空间上只需要两个计数器数组O(1)。这个复杂度在 LeetCode 上非常能打也是这道题最优雅的解法。3.2 用两个计数器维护窗口状态total 和 less具体实现时难点在于如何高效判断窗口是否合法。直接每次检查 26 种字符的计数有没有小于 k 的那就变成了 O(26n) 的检查虽然也能过但不够优雅。优化思路是维护两个变量total当前窗口内出现过的字符种类数。less当前窗口内出现次数小于 k 的字符种类数。窗口合法的充要条件是less 0。也就是说窗口内没有任何一种字符的出现次数小于 k。右指针扩展时字符c的计数加 1。这个变化可能影响两个变量如果计数从 0 变成 1说明窗口里多了一种字符total同时这种新字符当前次数是 1大概率小于 k所以less。如果计数从 k-1 变成 k说明这种字符从不达标变成了达标less--。注意只有当新计数恰好等于 k 时才需要减如果从 k 加到 k1它本来就已经达标了不需要重复减。左指针收缩时字符c的计数减 1。同样有两件事要处理如果计数从 k 变成 k-1这种字符从达标变成不达标less。如果计数从 1 变成 0这种字符从窗口里消失了total--同时它之前是不达标状态消失后less--。这里有个顺序问题值得注意当计数从 1 变成 0 时字符消失less要先减掉它原本贡献的不达标计数。如果你先做了total--再做less--不影响结果因为less的更新不依赖total的新值。但如果你漏掉了其中任何一步窗口状态就会失真整个滑动窗口逻辑就崩了。3.3 完整代码实现class Solution { public int longestSubstring(String s, int k) { int n s.length(); int answer 0; // 枚举窗口内允许出现的字符种类数 tt 的范围是 1 到 26 for (int t 1; t 26; t) { int[] count new int[26]; int left 0; int total 0; // 窗口内出现的字符种类数 int less 0; // 窗口内出现次数小于 k 的字符种类数 for (int right 0; right n; right) { int index s.charAt(right) - a; count[index]; // 新字符出现 if (count[index] 1) { total; less; } // 该字符从不达标变为达标 if (count[index] k) { less--; } // 窗口内字符种类数超过 t左指针收缩 while (total t) { int leftIndex s.charAt(left) - a; count[leftIndex]--; // 该字符从达标变为不达标 if (count[leftIndex] k - 1) { less; } // 该字符从窗口消失 if (count[leftIndex] 0) { total--; less--; } left; } // 窗口内所有出现过的字符都满足次数 k if (less 0) { answer Math.max(answer, right - left 1); } } } return answer; } }这段代码的核心逻辑全在total和less的维护上。右指针每走一步更新完计数后检查total是否超过t超过则收缩左指针。收缩完成后如果less 0说明当前窗口合法用窗口长度更新答案。一个容易被忽略但很关键的细节less 0时窗口一定合法但窗口内的字符种类数不一定恰好等于t。比如t 3当前窗口实际只有 1 种字符且这种字符出现次数大于等于 kless也是 0窗口同样是合法的。那这样会不会重复计算或漏算不会。因为我们在枚举t同一个合法窗口可能在多个t下都被检查到但题目只求最长长度重复检查不影响最大值。而最优解对应的窗口一定会在我们枚举到它的真实字符种类数时被捕获一次所以不会漏。3.4 双指针移动过程模拟拿一个具体例子模拟一遍你会更清楚这套逻辑的运作方式。假设s aaabbk 3枚举到t 1时初始left 0right从 0 开始移动。right 0字符a计数 1total 1less 1total没超过t但less ! 0不更新答案。right 1a计数 2由于计数不等于 kless仍为 1。right 2a计数 3恰好等于 k因新计数从 2 变 3less--此时less 0窗口[0, 2]长度为 3更新答案。right 3字符b计数 1total 2less 1但total t收缩左指针。left指向a计数从 3 变 2count k-1less此时less 2total仍为 2继续收缩。left再走一步另一个a计数从 2 变 1less不变total仍为 2继续收缩。left走到第三个a计数从 1 变 0total--less--此时total 1less 1停止收缩。窗口变成[3, 3]只有一个b自然不合法。继续移动右指针到末尾全程less再没变成 0最终t 1时答案是 3。枚举到t 2时右指针走完整个字符串都不需要收缩因为aaabb正好只有两种字符。整个字符串中a出现 3 次、b出现 2 次b小于 kless 1不合法。收缩左指针一步步把a减掉直到窗口只剩bbb只有 2 次还是小于 3less始终不为 0。最终t 2没有合法窗口。所有t枚举完全局答案就是 3对应aaa。这个模拟过程看起来繁琐但它展示了这套滑动窗口的精髓total控制窗口形状less判断窗口质量两者配合才能在 O(n) 时间内完成对单个t的完整扫描。4. 两种解法对比与面试答题策略4.1 从复杂度、实现难度、适用场景三个维度对比把两种解法的关键差异摊开来看对比维度分治法滑动窗口 枚举字符种类时间复杂度最坏 O(26n)常被描述为 O(n^2)严格 O(26n)常数略大空间复杂度O(26) 递归栈O(26) 计数数组实现难度中切割逻辑易出错中高计数器维护需理清是否依赖字符集大小依赖字符集越大递归深度越深依赖枚举次数等于字符集大小笔试可过性能过但复杂度不好解释能过且复杂度更稳面试印象分思路清晰加分算法功力展示强烈加分从纯算法角度讲分治法在字符集固定为 26 时复杂度也是线性的并不比滑动窗口差。但在面试场景下分治法最大的问题是你很难向面试官快速讲清楚为什么递归深度不会超过 26 层这个关键点。而滑动窗口解法只要你能把total和less的维护逻辑讲明白对方一听就懂代码也更有章法。4.2 面试时建议按这个顺序回答我建议的答题节奏是三步走。第一步先说暴力思路。枚举所有子串对每个子串检查是否合法时间复杂度 O(n^2) 的枚举加 O(26) 的检查总计 O(26n^2)不满足要求。第二步提出分治法。核心逻辑是坏字符切割。讲清楚为什么坏字符不能出现在任何合法子串中以及递归如何收敛。如果面试官追问复杂度顺带说明字符集大小 26 带来的递归深度上限。第三步如果有余力祭出滑动窗口 枚举字符种类数。重点强调标准滑动窗口失效是因为没有明确的收缩条件而固定字符种类数t恰好补上了这个条件。把total和less两个计数器的更新规则讲清楚面试官通常会眼前一亮。这个顺序展示的是你的思考递进过程而不是背题。面试官想看到的不是你做过这道题而是你能否从问题中发现套路。哪怕你只讲到分治法就卡住了前面的暴力思路和坏字符切割分析也已经体现了足够的算法素养。4.3 遇到变体题目怎么办这道题有不少变体理解了本质之后都不难应对。如果字符串不只包含小写字母而是任意 ASCII 字符滑动窗口的枚举范围从 26 改成 128 即可分治法则不受影响因为它的切割逻辑不依赖字符集大小。如果k非常大比如大于字符串长度那答案一定是 0可以在开头加一个剪枝。这个优化分治法和滑动窗口都能用。如果题目改成至少出现 k 次变体但限定的是子串中不同字符数不超过某个值那其实就是在原题基础上多套一层限制滑动窗口的total控制逻辑依然有效只是窗口合法的判断条件要额外加上不同字符数限制。这些变体本质上都是在回答同一个问题在一个连续区间上如何维护多种字符的频率约束。把total和less的维护逻辑理解透了换汤不换药。5. 常见问题与调试实录5.1 分治法为什么不会死循环很多人在写分治时担心一个问题如果每次找到的坏字符还是原来的字符递归会不会无限进行下去答案是不会。因为每次递归都会把当前区间按坏字符切割切割后产生的子区间中该坏字符的出现次数一定是 0它不可能再成为下一层的坏字符。而下一层如果出现新的坏字符那一定是一种新的字符。字符集只有 26 种所以递归深度最多 26 层。如果你在代码里加了区间长度小于 k 直接返回 0的剪枝递归会更早终止。我在初学这道题时曾经在切割循环里写过while (i right s.charAt(i) split) i;之后忘了继续判断i是否越界就直接取s.charAt(i)导致数组越界异常。调试了几分钟才反应过来。强烈建议每段代码里凡是用到索引取值的地方先确认索引在有效范围内。5.2 less 计数器更新顺序的经典错误滑动窗口解法里最容易被写错的是less的更新顺序。我见过不止一个同学在less--的条件上写错把count[index] k写成count[index] k。两种写法的差异在于如果某种字符已经达标次数从 k 变成 k1再变成 k2你只有第一次从 k-1 变到 k 时才应该让less--。如果写成 k每次计数增加都会触发less--那less会被减成负数整个判断逻辑全部失真。反过来左指针收缩时less的条件是计数从 k 变到 k-1不是从 k-1 变到 k-2。因为字符从达标变成不达标只有一次机会后续的减少只是让它更不达标不需要重复计数。这里用一个具体例子验证s aaaaaak 3窗口里只有a一种字符total 1less 0。右指针扩展a计数从 3 变 4如果你的代码在count k时执行less--那less就变成了 -1窗口明明合法却被判断为不合法答案就错了。5.3 枚举 t 的范围到底该取多大题目没有明确说明字符集只包含小写字母但 LeetCode 的测试用例实际上只包含小写英文字母。所以枚举t从 1 到 26 是安全的。但如果你在笔试环境里题目输入不可控稳妥做法是先扫描一遍字符串统计实际出现的字符种类数maxUnique然后枚举t从 1 到maxUnique。这样既是理论正确又能稍微减少一点常数开销。当然直接枚举到 26 也不会错最多多跑 26 次扫面对总复杂度没有影响。我建议在代码注释里写清楚这里假设输入只包含小写字母如果字符集不同枚举上界要相应调整这个细节在面试时主动提出来面试官会认可你的工程意识。5.4 如何快速判断选哪种解法我自己的经验法则很简单如果面试时已经提到了分治法面试官没有再追问更优解那就把分治法的代码写好把复杂度和边界条件讲透稳稳收工。如果面试官明确问能不能用滑动窗口或者题目要求的时间复杂度很苛刻直接上枚举字符种类数的方案。刷题阶段想加深理解可以两种解法都写一遍然后用随机生成的字符串做对拍验证。我自己写这道题时写过一个小脚本生成随机字符串把两种解法的输出逐个比对跑了上千组数据完全一致才敢说真正吃透了这道题。这个方法也推荐给正在刷题的你——用一个暴力解法和一个优化解法做对拍是验证算法正确性的最好工具。回到这道题本身最让我印象深刻的不是分治法的巧妙切割也不是滑动窗口的精准计数而是固定一个维度来让窗口约束变完整这个思路。很多看似没法用滑动窗口解决的问题只要你能找到一个可枚举的维度比如这里的字符种类数把问题降维成在一组固定约束下的滑动窗口解法就会自然浮现。类似的套路在 LeetCode 340至多 K 个不同字符的最长子串和 LeetCode 159至多两个不同字符的最长子串里也有体现建议连着刷对比着看收获会更大。 LeetCode 395：分治法和滑动窗口解决“每个字符至少出现k次”的最长子串问题
1. 题目到底在问什么拆解题意与核心难点1.1 先读懂题一个带着最少出现次数要求的最长区间问题LeetCode 395这道题题面很短但第一次接触的人很容易理解偏。原题描述是这样的给你一个字符串s和一个整数k请你找出s中的最长子串要求该子串中的每一个字符出现次数都不少于k。先抠字眼。子串意味着必须是连续的不是子序列所以排序、重新排列这类操作想都不用想。每一个字符指的是子串里真实出现的字符不是整个字符串里的所有字符。也就是说子串里出现的每种字母次数都要大于等于k。举个例子s aaabbk 3。整个字符串里a出现 3 次b出现 2 次。如果选整个字符串b只有 2 次小于 3不满足。那只能选aaa长度是 3这就是答案。再比如s ababbck 2。整个字符串里c只出现 1 次不满足去掉它剩下的ababb中a出现 2 次、b出现 3 次满足条件长度是 5。这类题目的本质是在一个字符串里找一个最长的连续区间使区间内的字符频率分布满足一个全局约束。你可以把它理解为带条件的最大窗口问题但这个条件不是加减法能直接判断的而是对窗口内所有字符做一次频率体检。1.2 为什么这题不是简单的滑动窗口刷过滑动窗口专题的人看到最长子串四个字第一反应就是双指针。但你要是直接套标准滑动窗口模板很快会发现不对劲。标准滑动窗口能工作的前提是窗口扩展和收缩时我们能明确判断当前窗口是否合法以及该不该移动左指针。比如 LeetCode 3 无重复字符的最长子串窗口是否合法取决于有没有重复字符右指针每走一步左指针可以跟着移动条件清晰。LeetCode 76 最小覆盖子串窗口是否合法取决于是否覆盖了目标字符集也是一个容易判断的布尔条件。但这题不一样。窗口的合法性取决于每种字符出现次数是否都大于等于 k而且这个约束没有明确的目标值可以比对。你想判断窗口合法至少需要知道窗口里有哪几种字符、每种出现几次、有没有低于 k 的。更麻烦的是一旦左指针收缩某个字符次数被减到 k 以下这个窗口立刻非法但你不知道到底该收缩到哪一步才算完。你可能会想那就让右指针一直走左指针在窗口不合法时收缩直到重新合法。问题来了什么时候算不合法比如k 3窗口里a有 2 次、b有 5 次这算不合法吧但收缩左指针应该删掉哪个字符删掉一个aa变成 1 次更不合法删掉一个bb变成 4 次窗口还是不合法。你没有一个明确的合法目标左指针的移动就失去了方向。所以这道题真正的难点不在滑动窗口本身而在于如何设计一个可控的窗口约束条件。理解了这一点后面的分治法和固定字符种类数滑动窗口解法你才能看出它们各自的设计动机。2. 解法一分治法——把大问题切到不能再切2.1 分治的核心思想找到一个坏字符分治法解决这题的切入点非常朴素如果一个字符在某个区间里出现的总次数小于 k那么任何包含这个字符的子串都不可能满足条件因为只要包含它它的出现次数就不可能高于它在整个区间里的次数。换句话讲这个坏字符就是天然的切割点。所有满足条件的子串一定分布在坏字符的左半边或右半边绝对不可能横跨它。于是问题被拆成了两个更小的子问题递归处理即可。看一下具体例子s abcabcabck 3。每个字符都出现了 3 次正好等于 k整个字符串就是答案长度 9。但如果s abcabcabk 3c只出现了 2 次小于 3那么任何包含c的子串都不行答案只能从被c切割出的若干段里找。按c切分后剩下的两段分别是ab和ab长度都只有 2小于 k直接返回 0。最终答案就是 0因为没有子串满足每个字符都出现至少 3 次。这个思路还有个可选的剪枝条件如果当前处理的区间长度本身就小于 k那无论如何都不可能满足条件直接返回 0。因为哪怕整个区间只有一种字符它也最多出现len次小于 k不满足要求。2.2 递归实现从统计频率到切割重组的完整流程我直接给出 Java 实现然后逐段拆解。class Solution { public int longestSubstring(String s, int k) { return dfs(s, 0, s.length() - 1, k); } private int dfs(String s, int left, int right, int k) { // 区间长度小于 k不可能满足条件 if (right - left 1 k) { return 0; } // 统计当前区间内每个字符的出现次数 int[] count new int[26]; for (int i left; i right; i) { count[s.charAt(i) - a]; } // 找出一个出现次数大于 0 但小于 k 的坏字符 char split 0; boolean valid true; for (int i 0; i 26; i) { if (count[i] 0 count[i] k) { split (char) (i a); valid false; break; } } // 如果当前区间所有字符出现次数都大于等于 k直接返回整个区间长度 if (valid) { return right - left 1; } // 以坏字符为分割点递归处理每一段 int i left; int result 0; while (i right) { // 跳过连续的坏字符 while (i right s.charAt(i) split) { i; } if (i right) { break; } int start i; // 找到这段的右边界遇到下一个坏字符为止 while (i right s.charAt(i) ! split) { i; } result Math.max(result, dfs(s, start, i - 1, k)); } return result; } }流程拆开是这样的第一步统计区间内每个字符的出现次数。这里用一个长度为 26 的数组因为题目默认字符串只包含小写字母。第二步扫描统计结果找到第一个出现次数大于 0 且小于 k 的字符。为什么是第一个因为只需要一个切割点。只要存在一个坏字符整个区间就不可能直接满足条件必须切分。选哪一个都行后续递归会处理其他坏字符。第三步如果扫描完发现所有出现过的字符次数都大于等于 k说明当前区间本身就是一个合法候选直接返回区间长度。第四步切割。从left到right扫一遍遇到坏字符就跳过把中间被分隔开的每一段递归处理取各段结果的最大值。这里有个很容易写错的点切割时不能简单地在坏字符的位置二分因为坏字符可能出现多次。你要做的是把区间按坏字符的所有出现位置切成若干段每一段单独递归。我的实现里用了一个嵌套 while 循环来定位每段的起止位置核心思路是找到一个非坏字符的位置作为起点向后扩展直到遇到坏字符或越界然后递归处理这一段。2.3 分治的复杂度与适用边界分治法的时间复杂度最坏情况下是 O(n^2)最好情况是 O(n)。为什么会有这么宽的波动关键取决于每次递归找到的坏字符能把区间切得多均匀。最坏的情况是每次切分只排除一个字符剩下的区间几乎没变小递归深度只有 26 层因为字符集只有 26 个字母每层至少排除一种字符但每一层的总扫描长度接近 n所以总体是 26 乘以 n 的量级。如果切分很均匀递归深度变成对数级别每一层总扫描长度还是 n复杂度接近 O(n log n)。很多资料说分治法最坏 O(n^2)其实在字符集大小固定为 26 的情况下最坏其实是 O(26n)也就是 O(n)。因为每次递归必然至少有一种字符被排除递归深度不可能超过字符集大小。这个细节面试时主动说出来面试官会认为你真的理解了这个算法的边界。空间复杂度方面递归栈深度最多 26加上每次递归创建长度为 26 的计数数组空间是 O(26) 常数级可以认为是 O(1)。分治法的优势是思路自然、代码直观适合在面试中作为第一个解答说出来。劣势是想证明复杂度时有点绕而且代码里切割逻辑如果写不熟练容易出 bug。我建议把分治作为保底方案真正想展示功底还是得看下一节的滑动窗口解法。3. 解法二滑动窗口 枚举字符种类数——面试官最想看到的答案3.1 标准滑动窗口失效的根源恰恰是解法的突破口前文说了标准滑动窗口失效是因为窗口的合法性条件没有明确的收缩目标。但如果换个思路窗口内出现的字符种类数是可以被固定的。设想一下如果我能控制窗口内恰好只允许出现t种字符在这个前提下找每种字符出现次数都大于等于 k的最长子串问题是不是就变得可解了因为t被固定后窗口的约束条件就完整了右指针扩展时如果窗口内字符种类数超过t左指针就得收缩直到种类数回到t以内。这就有了明确的收缩条件。而字符集只有 26 个小写字母t的取值范围是 1 到 26直接枚举所有t对每个t跑一次标准的滑动窗口全局最大值就是答案。这个思路第一次看到的人都会觉得这也能行但仔细想一下它是完全正确的。最优解对应的子串它的字符种类数一定是 1 到 26 中的某个整数。当我们枚举到那个整数时滑动窗口在遍历过程中一定能捕捉到该子串或者至少捕捉到一个不短于它的合法子串。所以最终答案不会漏。复杂度是多少每次滑动窗口是 O(n)枚举 26 次总复杂度 O(26n) O(n)。空间上只需要两个计数器数组O(1)。这个复杂度在 LeetCode 上非常能打也是这道题最优雅的解法。3.2 用两个计数器维护窗口状态total 和 less具体实现时难点在于如何高效判断窗口是否合法。直接每次检查 26 种字符的计数有没有小于 k 的那就变成了 O(26n) 的检查虽然也能过但不够优雅。优化思路是维护两个变量total当前窗口内出现过的字符种类数。less当前窗口内出现次数小于 k 的字符种类数。窗口合法的充要条件是less 0。也就是说窗口内没有任何一种字符的出现次数小于 k。右指针扩展时字符c的计数加 1。这个变化可能影响两个变量如果计数从 0 变成 1说明窗口里多了一种字符total同时这种新字符当前次数是 1大概率小于 k所以less。如果计数从 k-1 变成 k说明这种字符从不达标变成了达标less--。注意只有当新计数恰好等于 k 时才需要减如果从 k 加到 k1它本来就已经达标了不需要重复减。左指针收缩时字符c的计数减 1。同样有两件事要处理如果计数从 k 变成 k-1这种字符从达标变成不达标less。如果计数从 1 变成 0这种字符从窗口里消失了total--同时它之前是不达标状态消失后less--。这里有个顺序问题值得注意当计数从 1 变成 0 时字符消失less要先减掉它原本贡献的不达标计数。如果你先做了total--再做less--不影响结果因为less的更新不依赖total的新值。但如果你漏掉了其中任何一步窗口状态就会失真整个滑动窗口逻辑就崩了。3.3 完整代码实现class Solution { public int longestSubstring(String s, int k) { int n s.length(); int answer 0; // 枚举窗口内允许出现的字符种类数 tt 的范围是 1 到 26 for (int t 1; t 26; t) { int[] count new int[26]; int left 0; int total 0; // 窗口内出现的字符种类数 int less 0; // 窗口内出现次数小于 k 的字符种类数 for (int right 0; right n; right) { int index s.charAt(right) - a; count[index]; // 新字符出现 if (count[index] 1) { total; less; } // 该字符从不达标变为达标 if (count[index] k) { less--; } // 窗口内字符种类数超过 t左指针收缩 while (total t) { int leftIndex s.charAt(left) - a; count[leftIndex]--; // 该字符从达标变为不达标 if (count[leftIndex] k - 1) { less; } // 该字符从窗口消失 if (count[leftIndex] 0) { total--; less--; } left; } // 窗口内所有出现过的字符都满足次数 k if (less 0) { answer Math.max(answer, right - left 1); } } } return answer; } }这段代码的核心逻辑全在total和less的维护上。右指针每走一步更新完计数后检查total是否超过t超过则收缩左指针。收缩完成后如果less 0说明当前窗口合法用窗口长度更新答案。一个容易被忽略但很关键的细节less 0时窗口一定合法但窗口内的字符种类数不一定恰好等于t。比如t 3当前窗口实际只有 1 种字符且这种字符出现次数大于等于 kless也是 0窗口同样是合法的。那这样会不会重复计算或漏算不会。因为我们在枚举t同一个合法窗口可能在多个t下都被检查到但题目只求最长长度重复检查不影响最大值。而最优解对应的窗口一定会在我们枚举到它的真实字符种类数时被捕获一次所以不会漏。3.4 双指针移动过程模拟拿一个具体例子模拟一遍你会更清楚这套逻辑的运作方式。假设s aaabbk 3枚举到t 1时初始left 0right从 0 开始移动。right 0字符a计数 1total 1less 1total没超过t但less ! 0不更新答案。right 1a计数 2由于计数不等于 kless仍为 1。right 2a计数 3恰好等于 k因新计数从 2 变 3less--此时less 0窗口[0, 2]长度为 3更新答案。right 3字符b计数 1total 2less 1但total t收缩左指针。left指向a计数从 3 变 2count k-1less此时less 2total仍为 2继续收缩。left再走一步另一个a计数从 2 变 1less不变total仍为 2继续收缩。left走到第三个a计数从 1 变 0total--less--此时total 1less 1停止收缩。窗口变成[3, 3]只有一个b自然不合法。继续移动右指针到末尾全程less再没变成 0最终t 1时答案是 3。枚举到t 2时右指针走完整个字符串都不需要收缩因为aaabb正好只有两种字符。整个字符串中a出现 3 次、b出现 2 次b小于 kless 1不合法。收缩左指针一步步把a减掉直到窗口只剩bbb只有 2 次还是小于 3less始终不为 0。最终t 2没有合法窗口。所有t枚举完全局答案就是 3对应aaa。这个模拟过程看起来繁琐但它展示了这套滑动窗口的精髓total控制窗口形状less判断窗口质量两者配合才能在 O(n) 时间内完成对单个t的完整扫描。4. 两种解法对比与面试答题策略4.1 从复杂度、实现难度、适用场景三个维度对比把两种解法的关键差异摊开来看对比维度分治法滑动窗口 枚举字符种类时间复杂度最坏 O(26n)常被描述为 O(n^2)严格 O(26n)常数略大空间复杂度O(26) 递归栈O(26) 计数数组实现难度中切割逻辑易出错中高计数器维护需理清是否依赖字符集大小依赖字符集越大递归深度越深依赖枚举次数等于字符集大小笔试可过性能过但复杂度不好解释能过且复杂度更稳面试印象分思路清晰加分算法功力展示强烈加分从纯算法角度讲分治法在字符集固定为 26 时复杂度也是线性的并不比滑动窗口差。但在面试场景下分治法最大的问题是你很难向面试官快速讲清楚为什么递归深度不会超过 26 层这个关键点。而滑动窗口解法只要你能把total和less的维护逻辑讲明白对方一听就懂代码也更有章法。4.2 面试时建议按这个顺序回答我建议的答题节奏是三步走。第一步先说暴力思路。枚举所有子串对每个子串检查是否合法时间复杂度 O(n^2) 的枚举加 O(26) 的检查总计 O(26n^2)不满足要求。第二步提出分治法。核心逻辑是坏字符切割。讲清楚为什么坏字符不能出现在任何合法子串中以及递归如何收敛。如果面试官追问复杂度顺带说明字符集大小 26 带来的递归深度上限。第三步如果有余力祭出滑动窗口 枚举字符种类数。重点强调标准滑动窗口失效是因为没有明确的收缩条件而固定字符种类数t恰好补上了这个条件。把total和less两个计数器的更新规则讲清楚面试官通常会眼前一亮。这个顺序展示的是你的思考递进过程而不是背题。面试官想看到的不是你做过这道题而是你能否从问题中发现套路。哪怕你只讲到分治法就卡住了前面的暴力思路和坏字符切割分析也已经体现了足够的算法素养。4.3 遇到变体题目怎么办这道题有不少变体理解了本质之后都不难应对。如果字符串不只包含小写字母而是任意 ASCII 字符滑动窗口的枚举范围从 26 改成 128 即可分治法则不受影响因为它的切割逻辑不依赖字符集大小。如果k非常大比如大于字符串长度那答案一定是 0可以在开头加一个剪枝。这个优化分治法和滑动窗口都能用。如果题目改成至少出现 k 次变体但限定的是子串中不同字符数不超过某个值那其实就是在原题基础上多套一层限制滑动窗口的total控制逻辑依然有效只是窗口合法的判断条件要额外加上不同字符数限制。这些变体本质上都是在回答同一个问题在一个连续区间上如何维护多种字符的频率约束。把total和less的维护逻辑理解透了换汤不换药。5. 常见问题与调试实录5.1 分治法为什么不会死循环很多人在写分治时担心一个问题如果每次找到的坏字符还是原来的字符递归会不会无限进行下去答案是不会。因为每次递归都会把当前区间按坏字符切割切割后产生的子区间中该坏字符的出现次数一定是 0它不可能再成为下一层的坏字符。而下一层如果出现新的坏字符那一定是一种新的字符。字符集只有 26 种所以递归深度最多 26 层。如果你在代码里加了区间长度小于 k 直接返回 0的剪枝递归会更早终止。我在初学这道题时曾经在切割循环里写过while (i right s.charAt(i) split) i;之后忘了继续判断i是否越界就直接取s.charAt(i)导致数组越界异常。调试了几分钟才反应过来。强烈建议每段代码里凡是用到索引取值的地方先确认索引在有效范围内。5.2 less 计数器更新顺序的经典错误滑动窗口解法里最容易被写错的是less的更新顺序。我见过不止一个同学在less--的条件上写错把count[index] k写成count[index] k。两种写法的差异在于如果某种字符已经达标次数从 k 变成 k1再变成 k2你只有第一次从 k-1 变到 k 时才应该让less--。如果写成 k每次计数增加都会触发less--那less会被减成负数整个判断逻辑全部失真。反过来左指针收缩时less的条件是计数从 k 变到 k-1不是从 k-1 变到 k-2。因为字符从达标变成不达标只有一次机会后续的减少只是让它更不达标不需要重复计数。这里用一个具体例子验证s aaaaaak 3窗口里只有a一种字符total 1less 0。右指针扩展a计数从 3 变 4如果你的代码在count k时执行less--那less就变成了 -1窗口明明合法却被判断为不合法答案就错了。5.3 枚举 t 的范围到底该取多大题目没有明确说明字符集只包含小写字母但 LeetCode 的测试用例实际上只包含小写英文字母。所以枚举t从 1 到 26 是安全的。但如果你在笔试环境里题目输入不可控稳妥做法是先扫描一遍字符串统计实际出现的字符种类数maxUnique然后枚举t从 1 到maxUnique。这样既是理论正确又能稍微减少一点常数开销。当然直接枚举到 26 也不会错最多多跑 26 次扫面对总复杂度没有影响。我建议在代码注释里写清楚这里假设输入只包含小写字母如果字符集不同枚举上界要相应调整这个细节在面试时主动提出来面试官会认可你的工程意识。5.4 如何快速判断选哪种解法我自己的经验法则很简单如果面试时已经提到了分治法面试官没有再追问更优解那就把分治法的代码写好把复杂度和边界条件讲透稳稳收工。如果面试官明确问能不能用滑动窗口或者题目要求的时间复杂度很苛刻直接上枚举字符种类数的方案。刷题阶段想加深理解可以两种解法都写一遍然后用随机生成的字符串做对拍验证。我自己写这道题时写过一个小脚本生成随机字符串把两种解法的输出逐个比对跑了上千组数据完全一致才敢说真正吃透了这道题。这个方法也推荐给正在刷题的你——用一个暴力解法和一个优化解法做对拍是验证算法正确性的最好工具。回到这道题本身最让我印象深刻的不是分治法的巧妙切割也不是滑动窗口的精准计数而是固定一个维度来让窗口约束变完整这个思路。很多看似没法用滑动窗口解决的问题只要你能找到一个可枚举的维度比如这里的字符种类数把问题降维成在一组固定约束下的滑动窗口解法就会自然浮现。类似的套路在 LeetCode 340至多 K 个不同字符的最长子串和 LeetCode 159至多两个不同字符的最长子串里也有体现建议连着刷对比着看收获会更大。