LeetCode 题解工作台
划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"] ，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。 注意，划分结果需要满足：将所有划分…
4
题型
8
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们先用数组或哈希表 记录字符串 中每个字母最后一次出现的位置。 接下来我们使用贪心的方法，将字符串划分为尽可能多的片段。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec" 输出：[10]
提示：
1 <= s.length <= 500s仅由小写英文字母组成
解题思路
方法一：贪心
我们先用数组或哈希表 记录字符串 中每个字母最后一次出现的位置。
接下来我们使用贪心的方法，将字符串划分为尽可能多的片段。
从左到右遍历字符串 ，遍历的同时维护当前片段的开始下标 和结束下标 ，初始均为 。
对于每个访问到的字母 ，获取到最后一次出现的位置 。由于当前片段的结束下标一定不会小于 ，因此令 。
当访问到下标 时，意味着当前片段访问结束，当前片段的下标范围是 ，长度为 ，我们将其添加到结果数组中。然后令 , 继续寻找下一个片段。
重复上述过程，直至字符串遍历结束，即可得到所有片段的长度。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度，而 为字符集的大小。本题中 。
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)}
mx = j = 0
ans = []
for i, c in enumerate(s):
mx = max(mx, last[c])
if mx == i:
ans.append(i - j + 1)
j = i + 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each character is scanned once. Space complexity is O(k) where k is the number of unique lowercase letters, used for the hash map storing last occurrences. |
| 空间 | O(k) |
面试官常问的追问
外企场景- question_mark
Check if the candidate tracks last indices efficiently using a hash map.
- question_mark
Watch for correct handling of greedy expansion of partitions without missing characters.
- question_mark
Notice if candidate avoids unnecessary repeated scans of the same characters.
常见陷阱
外企场景- error
Failing to update the end pointer correctly when a character's last occurrence is beyond current end.
- error
Splitting partitions too early, causing repeated letters in multiple segments.
- error
Assuming contiguous letters must be grouped by first appearance only, ignoring last occurrence.
进阶变体
外企场景- arrow_right_alt
Partition a string where each letter can appear at most twice instead of once, adjusting partition expansion accordingly.
- arrow_right_alt
Return the actual substring partitions instead of sizes, requiring careful slice management during two-pointer scan.
- arrow_right_alt
Handle uppercase and lowercase letters distinctly while maintaining maximal partitioning logic.