前阵子整理贪心算法专题重新刷到“划分字母区间”这道经典题。说实话第一次做的时候我完全没把它当贪心题看按字符串模拟的思路折腾了半天提交后一堆用例超时。后来想明白核心思路才发现它其实是“跳跃游戏”那类覆盖式贪心的变体难度不大但特别考察对局部最优与全局约束的理解。这篇文章就把我踩过的坑和最终形成的解法拆开讲透适合刚开始刷贪心题、或者看完答案能 AC 但说不清为什么的读者。顺便说一句不同题库里这道题的编号可能标得不一样别纠结题号搜“划分字母区间”这个名字就好。面试里它经常作为二面算法题出现面试官喜欢让人讲清楚贪心为什么成立所以只会背题解远远不够。1. 这道题让很多人翻车的第一个原因把“片段最多”理解错了1.1 题面到底在说什么题目本身很短给定一个小写字母字符串 S把它划分成尽可能多的片段要求同一个字母只能出现在其中一个片段中最后返回每个片段长度的列表。关键点有两个。第一个是“尽可能多”第二个是“同一个字母只能出现在其中一个片段中”。很多人一看“尽可能多”下意识就觉得“切得越碎越好”于是开始想怎么把字符串拆成尽量多的小段。这个直觉不能说错但会把人带偏。看标准样例就清楚了S ababcbacadefegdehijhklij正确答案是[9, 7, 8]也就是切成三段ababcbaca、defegde、hijhklij。注意第一段里出现了 a、b、c这三个字母在整个字符串里出现的位置都被限制在前 9 个字符以内所以第一片段的右边界至少要到下标 8。第二段里出现了 d、e、f、g这四个字母在整个字符串里的所有出现又恰好都在下标 9 到 15 之间。第三段同理。换句话说这道题要的不是“把一个字符集合能拆得多碎”而是“在必须把同类元素绑在一起的前提下最多能分成几组”。一旦某个字母进了某个片段它在整串中所有出现都必须跟着进这个片段这就是最硬性的约束。1.2 常见错误思路和它们的死因我见过不少人在错误思路上打转典型的有三种。第一种是统计字符出现次数想用次数判断一个片段是否“完整”。比如数出 a 出现 4 次、b 出现 3 次然后从左往右扫攒够了数量就尝试切一刀。这种做法看着合理其实根本站不住脚约束条件是“位置”不是“数量”。一个字符即使只出现两次也可能一个在最左边一个在最右边把整段都撑开反过来一个字符出现很多次也可能集中在一小段里。用频率做分割依据本质上是把二维的位置信息压缩成了一维的数量信息信息量不够必然出错。第二种是回溯枚举所有切割方案。先找到所有可能的切割位置然后用 DFS 或 DP 尝试每一种切法检查是否满足“同一字母只出现在一个片段”最后取片段数最多的方案。这个思路在正确性上没问题但复杂度是灾难性的。长度为 n 的字符串切割点有 n-1 个每个点都有“切”和“不切”两种选择枚举规模是 2^(n-1)。题目给到几百的长度时这个方案基本等于超时。它更适合作为小规模数据的验证工具而不适合作为正解。第三种是在“片段最多”上做文章想把片段长度切得均匀一点比如两两配对、前后对称。这种想法属于脑补额外条件。题目只要片段数量最多不要求长度均匀你加入均匀性约束等于给问题加了不存在的限制答案自然可能出错。我当初就栽在第二种思路上以为这题是搜索题写了两百多行代码最后还被面试官点了一句“你能不能想想为什么不需要回溯”。后来才意识到这个问题的约束其实非常强强到根本不用试错直接一路贪过去就能得到最优解。2. 解题灵魂用每个字母的“最后出现位置”当锚点2.1 把一个字符的问题翻译成区间问题想通这道题首先要换一个角度看。对任意一个字符 ch它在字符串中第一次出现的位置是 first最后一次出现的位置是 last。既然“同一个字母只能出现在一个片段里”那么包含 ch 的片段右边界无论如何都不可能小于 last。因为如果片段在 last 之前就结束了ch 在 last 位置又出现了一次就会被分到后面的片段违反规则。进一步想ch 的约束其实形成了一个天然区间[first, last]。一个合法的片段要么完整覆盖这个区间要么和这个区间完全不沾边。所以整个问题可以重新表述成为字符串里的每个不同字符画一条从首次出现到末次出现的线段然后把所有相互重叠、相互接触的线段合并合并后每个区间就是一个片段。这个视角特别重要因为它解释了为什么这个问题不需要回溯。每个字符的区间是固定的不会因为你选择了某种切割方式就改变。既然区间固定合并的结果就是唯一的不存在“试了这种切法能得到 3 段、换种切法能得到 4 段”的空间。回溯之所以多余正是因为答案没有分叉。2.2 用“不得不扩展”来理解贪心为什么成立现在只看最后一次出现的位置。假设当前片段的起点是 start那么第一个字符 S[start] 已经被放入当前片段它的最后一次出现位置是last[S[start]]所以当前片段的右边界至少要是这个位置。把 end 初始化成它。然后从 start 往右扫描。在扫描过程中每遇到一个字符 ch就检查它的last[ch]是否比当前的 end 更大。如果更大说明这个字符在后面还有出现而它又已经在本片段里出现了因此本片段的右边界被迫向右扩展到last[ch]。这个过程很像打包行李只要箱子里有一件东西后面还要用你就不能提前封箱只有把所有已装物品的最后需求都考虑完才能封箱。这里也一样end 被不断拉大直到扫描到 end 位置时发现 end 不再增长此时才说明“当前已经装入片段的所有字符它们的最后一次出现都不超出 end”可以安全切割。为什么这就是最优做一个简短的反证。如果存在某个合法切分它的第一段右边界 r 小于我们算出的 end那么会有一个字符 x 在本段内出现假设位置是 k且 k r而 x 的最后一次出现位置last[x]大于 r。x 在本次出现之后又会在后面出现于是同一个字母 x 就同时出现在第一段和后面的段违反了“同一字母只能在一个片段”的条件。也就是说任何合法切分的首段右边界都不可能小于 end。那我们直接取 end 作为首段右边界不仅合法而且不会让可行方案变少。首段确定后从 end1 开始继续同样的贪心过程每一步都是同样的逻辑。局部上“不得不扩展到最大”全局上也不会吃亏这就是标准的贪心证明思路。3. 两遍扫描代码能短到吓人3.1 完整代码与逐行解释代码的核心分两步第一遍扫描记录每个字符最后一次出现的位置第二遍扫描维护 end 并在到达 end 时切段。下面是 Python 版本。class Solution: def partitionLabels(self, s: str) - List[int]: # 第一遍记录每个字符最后出现的下标 last [0] * 26 for i, ch in enumerate(s): last[ord(ch) - ord(a)] i ans [] start 0 end 0 # 第二遍从左向右扫描不断拉大 end到点切割 for i, ch in enumerate(s): end max(end, last[ord(ch) - ord(a)]) if i end: ans.append(end - start 1) start end 1 return ans这里有一个细节值得注意第二次循环里end是单调不减的。切完一个片段之后我没有把end清零而是让它继续带着旧值参与下一轮的max。很多人第一次看这段代码会疑惑第二段的 end 起点为什么是 8 而不是 0实际上旧值不会造成问题因为下一段只要遇到任何一个字符它的last就会覆盖旧值而如果下一段所有字符的 last 都比旧值小那说明这个片段根本不可能在旧 end 之后合法存在这种情况不会发生。不过为了自己写代码时思路更清晰切成ans.append(end - start 1); start end 1之后手动加一句end i也是完全等价的只是多写一行而已。3.2 用标准样例完整推演一遍还是用官方样例S ababcbacadefegdehijhklij。先看第一遍扫描后记录到的最后出现位置。字符abcdefghijkllast 下标857141511131922232021然后看第二遍扫描的关键轮次。注意 start 和 end 的联动。i字符last[ch]end 变化动作0a80 - 8第一段起点end 被 a 拉到 84c7max(8,7)8a、b、c 都在段内end 不动8a8max(8,8)8i end切第一段长度 99d14max(8,14)14第二段起点d 把 end 拉到 1412e15max(14,15)15e 把 end 拉到 1515e15max(15,15)15i end切第二段长度 716h19max(15,19)19第三段起点h 拉到 1917i22max(19,22)22i 把边界拉到 2218j23max(22,23)23j 一口气拉到 2323j23max(23,23)23i end切第三段长度 8最终得到[9, 7, 8]和样例一致。整个过程里最值得体会的是end 并不是一步步涨上去的而是被某些“拖后腿”的字符一下子拉远。比如第一段的 end 从 0 直接跳到 8中间 b、c 都没能撼动它第三段则被 j 直接拉到 23之后的 h、k、l 全都只是陪跑。3.3 边界用例空串、单字符、全同、全异边界情况能暴露很多实现问题建议刷完这道题后把这几个用例都过一遍。空串第一遍循环不执行第二遍也不执行直接返回[]。Python 里last数组全是 0不会报错。单字符alast[a] 0第二遍 i0 时 end 从 0 变 0切出[1]。全相同字符aaaalast[a] 3end 一上来就是 3直到 i3 才切割返回[4]。这个用例特别能纠正“片段多 切得碎”的错误直觉无论怎么切a 的出没范围都要求它只能在一个片段里所以整串必须是一段。全不同字符abcdef每个字符的 last 都等于自己的下标于是每轮 i end切出[1,1,1,1,1,1]。这是片段数量的理论上限因为没有字符会在后面重复出现约束形同虚设。再来一个反直觉的caacbc 的最后位置是 2a 的最后位置是 3b 的最后位置是 4。第二遍扫描时i0 时 end 被 c 拉到 2i1 时 a 把 end 拉到 3i2 时 c 不能动 endi3 时 a 也不能动 end但 i4 时 b 把 end 拉到 4此时才切割整体返回[5]。这说明 b 虽然只出现一次但因为它出现在下标 4就把整个段拖满了。一个字符哪怕只出现一次只要位置靠后同样能成为片段的边界锚点。4. 复杂度、边界条件和面试官的连环追问4.1 时间与空间复杂度算给你看时间复杂度是 O(n)n 是字符串长度。第一遍遍历记录 last第二遍遍历扫描切段每一轮都是常数操作所以总开销是 2n 的量级。空间复杂度这里值得多说一句。如果按“哈希表存字符下标”来理解空间是 O(σ)σ 是字符串中不同字符的个数。但由于题目限制为小写字母σ 最大只有 26所以严格来说空间是 O(1)。如果面试时你回答“空间复杂度 O(n)”大概率会被追问存储的是字符串长度的量还是字符类型的量用固定数组而不是字典一眼就能看出空间和字符串长短无关这也是很多人推荐数组写法的原因。原题字符串只含小写字母所以数组版本里用ord(ch) - ord(a)做索引很安全。如果题目条件放宽允许大写字母甚至任意 Unicode 字符那就改成字典last {}思路完全不变只是空间从固定 26 变成按字符种类增长。用字典的版本我会写成last {} for i, ch in enumerate(s): last[ch] i查询时end max(end, last[ch])即可。这类题目用字典反而更通用面试官问起来也更好解释。4.2 面试官爱问的 5 个问题我汇总了几个常见的追问建议提前想清楚回答不要卡壳。为什么不能一趟扫描就完成 因为切片的边界取决于“某个字符未来还会不会出现”而未来信息只有在扫描到末尾之后才知道。第二遍扫描本质上是在“全知”的状态下做决策这是离线算法。如果只允许一趟扫描相当于流式处理单凭当前位置和过往位置无法判断一个字符是否已经全部出现完。所以预处理 last 这一步不是优化而是必要前提。切完一段之后 end 要不要清零 清零不清零结果一样。我在代码里倾向于不清零利用max的单调性省一行。但如果你笔试时怕解释不清楚可以在切段后写end i效果等价。重点是你得知道这两者为什么等价而不是死记某一种写法。原题返回长度如果想返回片段内容怎么办 改成ans.append(s[start:end1])就行。返回内容和返回长度在切割点上没有任何区别只是存储的数据类型不同面试官这么问通常是想确认你是否理解了切片区间是闭区间。如果字符串包含大写字母或者中文字符呢 用字典替代固定数组每个字符的最后出现位置照常记录。算法的时间复杂度仍是 O(n)空间复杂度变成 O(σ)不再能说 O(1)。为什么这道题归类为贪心而不是模拟 因为每一段的右边界都是“当前必须扩展到的最大位置”这一步选择不回溯、不试错直接根据全局信息和当前状态做局部最优决策而且能证明局部最优累积成全局最优。这正是贪心算法的定义特征。模拟通常指按规则机械推进不涉及这种“最优性论证”。5. 和合并区间、跳跃游戏放在一起看思路一下就通了5.1 从区间合并视角重新审视这道题我前面提到把每个字符映射成[first, last]的区间后问题就变成区间合并。这里补一个更重的写法虽然不如贪心简洁但特别适合用来理解等价关系。def by_intervals(s): first {} last {} for i, ch in enumerate(s): if ch not in first: first[ch] i last[ch] i intervals [(first[ch], last[ch]) for ch in first] intervals.sort() merged [] for l, r in intervals: if not merged or l merged[-1][1]: merged.append([l, r]) else: merged[-1][1] max(merged[-1][1], r) return [r - l 1 for l, r in merged]这个版本的复杂度包含一个排序整体是 O(σ log σ n)。由于 σ 很小实际也很快。但它最大的价值是让你看到一个事实每个字符的首次出现和末次出现固定以后所有区间的并集和重叠关系是客观存在的。贪心解法其实就是在这个区间合并的基础上利用“字符串从左到右的顺序天然是区间起点顺序”来省掉排序。想通了这一点面试的时候不管面试官从哪个角度切入你都能接住。5.2 与跳跃游戏 II 的类比力扣的跳跃游戏 II 是另一个让我印象深刻的覆盖型贪心。在那道题里你在每个位置 i 能跳到的最大距离是i nums[i]当前跳跃能覆盖的边界之内你不断更新“下一步能到达的最远位置”到达边界后步数加一。这道题几乎一模一样。每个字符 ch 的last[ch]就是一个“绝对坐标下的最远落点”你在当前片段的边界内扫描时不断用last[ch]更新“本片段最终能到达的最远位置”到达边界后切一刀、计一段。区别只是跳跃游戏关注“最少跳几次”这里关注“最多切几段”跳跃游戏里每一步有多个可选落脚点这里每个位置只有一个字符、一个 last 值。模式识别一旦建立下次遇到“给你一堆元素每个元素有约束范围问能分成几组”的题第一反应就应该是覆盖式贪心。5.3 现实业务里的映射这类“按元素最大跨度分组”的问题在工程里其实有影子。比如日志清洗时一个请求会分成多行日志输出我们想把同一个请求 ID 的所有日志行聚合到一个切片里就需要先统计每个请求 ID 最后出现的行号然后按行号切分。再比如广告投放里需要把同一个用户在某个时间窗内的所有触达记录归并成一个会话同样是“同类元素只能在同组”的约束。算法题的价值很多时候不在于它本身而在于它训练你看到“相同结构”的能力。一个能在字符串上快速抽象出覆盖区间的人面对这些业务问题也会本能地去找“每个元素的最后出现位置”。6. 我踩过的坑和一套自测方法6.1 三个容易写错的实现细节第一start更新错位置。切成start end而不是start end 1。看着只差一个 1但会导致下一个片段的起点和上一个片段的终点重叠片段长度全部错乱。这种 bug 在样例a上可能测不出来因为end - start 1会变成负值样例一跑直接崩反而算好事。第二使用字典时误把“首次出现位置”当“最后出现位置”。有朋友为了省一次遍历在第二遍循环里用last.get(ch, i)来更新 end得出的 end 会偏小。因为get只会在键不存在时返回 i而键存在时返回的是第一遍记录的旧值这其实就是想要的值。但如果不小心写成last[ch] i再取last[ch]那就把字典在第二遍里又改了一遍最后得到的是当前位置而不是末次位置。我在帮人 review 代码时见过这种写法很隐蔽建议写完立刻用ababcbacadefegdehijhklij自测。第三数组索引忘减字符偏移。比如写last[ord(ch) - 97]没问题但写成last[ch]或者last[ord(ch)]会直接越界或者取到错误位置。这类问题最有效的预防方式是统一用一个常量表示ord(a)或者直接写成ord(ch) - ord(a)可读性更好。6.2 用暴力枚举脚本交叉验证刷题最怕“脑补正确”。我现在的习惯是遇到这种贪心题先写一个暴力枚举版本用于小规模测试再用随机数据对拍。下面这个暴力版穷举了所有切割方案只适合长度很小的字符串但用来验证贪心正确性非常够用。from itertools import combinations def brute(s): n len(s) best_len 0 best None for k in range(1, n 1): for cuts in combinations(range(1, n), k - 1): segs [] prev 0 for c in cuts (n,): segs.append(s[prev:c]) prev c char_sets [set(seg) for seg in segs] ok True for i in range(len(char_sets)): for j in range(i 1, len(char_sets)): if char_sets[i] char_sets[j]: ok False break if not ok: break if ok and len(segs) best_len: best_len len(segs) best [len(seg) for seg in segs] return best or []对拍的时候可以随机生成小写字母组成的短字符串长度控制在 1 到 12因为暴力枚举的量级是 2^(n-1)。比如生成 200 组随机样例把partitionLabels和brute的结果逐一对比。我最初写出来的贪心代码一直正确但有一次随机生成到caacb这类数据时我才真正注意到 b 这种“只出现一次但位置靠后”的字符也能拖动整段边界。这个发现比单纯 AC 更有价值因为它帮我建立了对覆盖式贪心的直觉。6.3 一个有效的学习习惯看看“最远的那个字符”现在遇到任何区间分组、覆盖型问题我会习惯性地问自己三个问题每个元素的最后位置是多少当前组必须覆盖到的最远点是多少到达这个最远点时能不能安全收拢如果三个问题都有明确答案那大概率就不需要回溯或动态规划。这道“划分字母区间”给我最大的启发不是那十几行代码而是“片段最多”和“切得碎”之间的微妙差别。真正想让片段数量多反而要让每个片段尽量长地把同类约束吸收干净把一个字母的所有出现都捂在同一个片段里。这个经验和直觉后来在处理很多资源分组、任务分区的问题时都用得上。刷题刷到最后记住的不是题号而是这种“看问题结构”的方式。