763. 划分字母区间 (Medium)
专题归类： 11-贪心 LeetCode 链接： https://leetcode.cn/problems/partition-labels/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个字符串 s，你要把这个字符串分割成尽可能多的片段，使得同一个字母最多出现在一个片段中。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec"
输出：[10]
题目详细分析
数据范围： 1 <= s.length <= 500，s 仅包含小写英文字母（‘a’ ~ ‘z’）
核心约束：
- 同一个字符不能跨越两个片段——如果字符 ‘a’ 出现在位置 0 和位置 5，那么整个
[0, 5]必须在同一个片段内 - 目标是片段数量最大化，即在满足约束的前提下尽量多地切分
- 返回的是每个片段的长度，而非起始/结束下标
关键洞察：
- 每个字符的最后出现位置决定了该字符所在片段的右边界
- 问题可转化为区间合并：每个字符的首次出现和最后出现形成一个区间
[first, last]，问题变成合并所有重叠区间 - 贪心策略：遍历字符串时不断扩展当前片段的右边界，当遍历到边界时切分
小白版直白理解
就像你在整理一堆积木，每个积木上写了一个字母。你想把它们分成几堆，但有个规矩：同一个字母的所有积木必须在同一堆里，不能分开。你想尽可能多分几堆。
比如 “ababcbacadefegdehijhklij”：
- 字母 ‘a’ 出现在开头和中间某个位置，所以从 ‘a’ 第一次出现到最后一次出现的这一段，必须打包在一起
- 字母 ‘b’、‘c’ 也在这个范围内，连带着它们的最后出现位置也会把边界推得更远
- 最终第一段边界被推到位置 8（即 “ababcbaca”）
- 然后从位置 9 开始同样的过程…
你只需要关注每个字母最后一次出现的位置——它在哪，就决定了包含这个字母的片段至少得延伸到哪里。
解题思路
思路一：贪心 + 最后位置表（推荐）
思路讲解： 分两步走：
第一步（预处理）： 遍历一次字符串，用哈希表（或长度为 26 的数组）记录每个字符最后出现的下标。
第二步（贪心切割）： 再次遍历字符串，维护：
start：当前片段的起始位置end：当前片段的右边界（动态扩展）- 每遇到一个字符
c，就将end更新为max(end, last[c]) - 当
i == end时，说明当前片段结束，记录长度end - start + 1，然后start = i + 1开始下一个片段
为什么贪心是对的？ 每个字符的”最后出现位置”是不可妥协的硬约束，在满足约束的前提下，尽早切分（i == end 时立即切）能得到最多片段，局部最优（尽早切）就是全局最优（片段最多）。
def partitionLabels(s):
# 第一步：记录每个字符最后出现的位置
last = {c: i for i, c in enumerate(s)}
ans = []
start = end = 0
# 第二步：遍历字符串，贪心切割
for i, c in enumerate(s):
end = max(end, last[c]) # 不断扩展当前片段的右边界
if i == end: # 到达当前片段的右边界，切分
ans.append(end - start + 1)
start = i + 1 # 下一片段起点
return ans时间复杂度： O(n)（两次遍历） | 空间复杂度： O(26) = O(1)
思路二：区间合并
思路讲解： 将每个字符的首次出现位置和最后出现位置看作一个区间 [first, last]。然后对所有区间按起始位置排序，执行标准的区间合并——合并所有重叠的区间。合并后的每个区间就是一个片段。这个方法更通用，但代码稍长。
def partitionLabels(s):
# 记录每个字符的首末位置
first = {}
last = {}
for i, c in enumerate(s):
if c not in first:
first[c] = i
last[c] = i
# 构造区间并排序
intervals = [(first[c], last[c]) for c 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(n + k log k)，k 为不同字符数（最多 26） | 空间复杂度： O(k)
易错点
- 更新
end时用last[c]而非i：last[c]是字符 c 的最后出现位置，不能写成end = max(end, i) - 切分时机：必须在
i == end时切分。如果提前切分，同一个字母可能出现在多个片段中；如果延后切分，片段数会减少 start的更新：切分后start = i + 1，注意不是start = end + 1（虽然此时i == end，但语义上应该是下一个位置）s长度可能为 1：这时应该返回[1]，代码应能正确处理- 所有字符都相同的情况：如
"aaaa"，整个字符串只有一个片段[4] - 不区分大小写：题目字符串仅包含小写字母，无需考虑大小写
框架提炼
贪心模板：基于”最后位置”的区间划分
def partitionByLast(s):
# 1. 预处理：记录每个字符的最后出现位置
last_pos = {}
for i, c in enumerate(s):
last_pos[c] = i
# 2. 贪心切割
ans = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last_pos[c]) # 扩展右边界
if i == end: # 可切分
ans.append(end - start + 1)
start = i + 1
return ans核心思想： 遍历 + 动态扩展右边界，当遍历到下界时切分。适用于”区间合并”类问题——每个元素定义了它必须属于的区间范围，合并重叠区间后得到最终划分。
这种”先记录位置，再遍历切分”的模板也适用于：
- 合并重叠区间（先排序再合并）
- 会议室问题（判断区间是否重叠）
- 字符串解码中的括号匹配（匹配最近括号时扩展右边界）
关联题目
- 56-合并区间 — 更通用的区间合并问题，先排序再合并
- 452-用最少数量的箭引爆气球 — 区间重叠问题，按右端点排序的贪心
- 435-无重叠区间 — 求移除最小区间使剩余区间不重叠
- 55-跳跃游戏 — 同样是”扩展最远可达距离”的贪心思想，和本题的”扩展右边界”异曲同工