跳到正文
第 763 题中等

划分字母区间

Partition Labels

把字符串划分成尽量多的片段，使同一字母只出现在一个片段中；返回每个片段的长度。

在力扣中练习

题目描述

给你一个字符串 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 <= 500
  • s 仅由小写英文字母组成

解题思路

主解法

最后位置 + 贪心扩展

当前段必须覆盖段内每个字符的最后出现位置

如果从 start 开始切一段，那么段内出现的每个字符，它的最后一次出现也必须在段内；否则同一个字母会被分到两个段里。

先统计每个字符的最后位置。扫描时维护当前段的 end，每读到一个字符就用它的最后位置更新 end = max(end, last[c])。

分步图解

最后位置：a=2，b=1，c=3，d=5，e=7；end 初始为 0。

start
0
当前段 [0,0]
0
1
2
3
4
5
6
7
astart
b
a
c
d
d
e
e
当前段的 end 必须覆盖段内每个字符最后出现的位置。
res · 每段长度
[ ]
每个字符最后出现的位置
a→2
b→1
c→3
d→5
e→7
1 / 4
end 随着字符最后位置不断右移，直到 i 追上 end 才能切段。

当 i == end 时，说明当前段的所有字符都不会再出现在后面，可以切一刀；记录长度，start 移到 i+1。

分步图解

i=3 字符 c 的最后位置是 3，end 2 → 3；i 已到段尾，切出长度 1，start 移到 4。

start
3
end
3
当前段 [3,3]
0
1
2
3
4
5
6
7
a
b
a
cstart
d
d
e
e
i
当前段的 end 必须覆盖段内每个字符最后出现的位置。
res · 每段长度
31
每个字符最后出现的位置
a→2
b→1
c→3
d→5
e→7
1 / 4
c 单独成段；d、e 各自覆盖到自己的最后位置，得到 [3,1,2,2]。

自拟串 "abacddee"：a 的最后位置是 2，所以第一段必须包含 aba；c 独立；d、e 各自覆盖到自己的最后位置，得到 [3,1,2,2]。

时间 O(n)，空间 O(1)（只固定 26 个字母的最后位置）。

时间 O(n)空间 O(1)

易错点

  • 用第一次出现的位置当边界：段内后续字符可能延伸到更远。
  • i == end 时忘记更新 start：下一段长度会从 0 重新算。
  • 只统计段内字符集合，不维护 end：无法判断何时可以安全切段。

代码与演示

演示输入s = "abacddee"

先统计每个字符最后出现的位置；扫描时，当前段的 end 要不断取最大值。

当前段 [0,0]
0
1
2
3
4
5
6
7
astart
b
a
c
d
d
e
e
当前段的 end 必须覆盖段内每个字符最后出现的位置。
res · 每段长度
[ ]
每个字符最后出现的位置
a→2
b→1
c→3
d→5
e→7
1 / 7
查看 C++ 代码

延伸阅读

  • 划分字母区间本质是“合并有重叠的区间”：每个字符的区间是 [第一次出现, 最后一次出现]。
  • 同类思路可以处理区间合并、任务调度等需要“当前区间必须覆盖某些点”的问题。