LeetCode 763. 划分字母区间
题目描述
题意分析
把整个字符串按原顺序切成若干非空的连续片段，所有片段拼回去必须仍是原字符串。同一个字母可以在一段内出现多次，但它的所有出现位置必须放在同一段，不能分散到不同片段。
在满足限制的前提下，片段数量要尽可能多，最后按顺序返回各段长度。只保证每段合法还不够：把整个字符串当成一段总是合法，却未必达到最多段数。
解法：记录最后位置后贪心切分
核心思路
[!blue]
如果当前片段已经包含字母
c，它就必须延伸到c最后一次出现的位置，否则剩余的c会落到后面的片段中。先用last[c]记录每个字母的最后下标，再从左向右确定切点。用
start记录当前片段起点，end记录这一段已经出现过的所有字母的最远末次位置。扫描到i时，将end更新为max(end, last[s[i]])。向右延伸途中可能遇到新的字母，新字母又可能把边界推得更远，所以不能仅根据首字母的末次位置直接切分。当
i < end时，当前片段中至少有一个字母还会在后面出现，此处不能切。当i == end时，已经扫描了整个候选片段，其中每个字母的最后出现位置都不超过end，此时切分一定合法。这个切点也是当前能选择的最早合法位置。任何合法划分都不能更早结束这一段；若某个划分在更晚的位置才切，仍可在这里增加一个切点，因为前段的字母不会再出现，后面的片段不受影响。因此找到合法边界就立即切开，能够得到最多的片段。
解题步骤
- 扫描字符串，使用长度为
26的数组last记录每个小写字母的最后下标。- 初始化
start = 0、end = 0，准备保存片段长度的结果列表。- 再次扫描字符串，每读到一个字母，将
end扩展到当前值与该字母最后下标的较大者。- 若当前下标
i == end，记录长度end - start + 1，并令start = i + 1，开始寻找下一段。- 扫描结束返回长度列表。最后一个下标必然满足边界条件，因此不需要另补末段。
代码实现
class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> ans = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last[s.charAt(i) - 'a']);
// 当前段出现过的全部字符都已收齐，立刻切分才能得到最多段。
if (i == end) {
ans.add(end - start + 1);
start = i + 1;
}
}
return ans;
}
}
func partitionLabels(s string) []int {
last := [26]int{}
for i := 0; i < len(s); i++ {
last[s[i]-'a'] = i
}
ans := make([]int, 0)
start, end := 0, 0
for i := 0; i < len(s); i++ {
if last[s[i]-'a'] > end {
end = last[s[i]-'a']
}
// 当前段出现过的全部字符都已收齐，立刻切分才能得到最多段。
if i == end {
ans = append(ans, end-start+1)
start = i + 1
}
}
return ans
}
复杂度分析
- 时间复杂度：
O(n)。统计最后位置和确定切点各扫描一次字符串，每次更新为常数操作。- 空间复杂度：
O(1)。辅助数组固定为26个位置；返回结果不计入额外空间。
关键点总结
[!green]
- 每个已出现的字母都对当前段的右边界提出约束，
end必须满足所有约束。end是尚不能越过的最远位置，会随着新字母的出现继续扩张。- 到达边界立即切分既保证合法，也保留了后续能够增加切点的全部机会。
易错点总结
[!yellow]
- 记录首次位置而不是末次位置：无法知道当前字母是否还会在后续片段出现。
- 直接把
end赋成当前字母的末次位置：边界可能回退，丢掉此前其他字母的约束，必须取最大值。- 只检查当前字母是否最后一次出现：当前片段内其他字母也必须全部出现完，判断条件是
i == end。- 边统计末次位置边切分：未扫描的后缀仍可能包含当前字母，需要先完成预处理。
- 长度和起点偏移一位：当前段包含两个端点，长度为
end - start + 1；下一段从i + 1开始。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 56. 合并区间 | 中等 | 每个字符的首次到末次位置形成约束区间，重叠约束必须合并进同一段。 |
| 768. 最多能完成排序的块 II | 困难 | 同样寻找不会影响其他区间的安全切点，原题禁止排序关系跨块，本题禁止同一字符跨段。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！