763. 划分字母区间
题目描述
输入字符串 s。把它从左到右切成若干段，各段按原顺序拼起来仍是 s。
要求每个字母只出现在其中一段里，也就是说同一个字母的所有出现位置必须落在同一段内。在满足要求的前提下，段数要尽量多。
按从左到右的顺序返回每一段的长度。
示例 1
输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8]
解释：切成 "ababcbaca"、"defegde"、"hijhklij"，每个字母只在一段中出现。
示例 2
输入：s = "eccbbbbdec" 输出：[10]
解释：字母 e 和 c 横跨首尾，整个字符串只能作为一段。
数据范围
1 <= s.length <= 500s只含小写英文字母。
解题思路
先记录每个字母最后出现位置，再扫描并扩展当前片段右边界；扫描到边界时切分。
为什么正确
当前片段内所有字符的最后出现位置都不超过 right，故在 right 处切分安全。
复杂度分析
时间 O(n)，空间 O(字母表)。
易错点
只按当前字符是否重复来切分不够，必须使用每个字符的最后出现位置。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
from typing import List
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {ch: i for i, ch in enumerate(s)}
result = []
start = right = 0
for i, ch in enumerate(s):
right = max(right, last[ch])
if i == right:
result.append(i - start + 1)
start = i + 1
return resultclass Solution {
public List<Integer> partitionLabels(String s) {
Map<Character, Integer> last = new HashMap<>();
for (int i = 0; i < s.length(); i++) last.put(s.charAt(i), i);
List<Integer> result = new ArrayList<>();
int start = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
right = Math.max(right, last.get(s.charAt(i)));
if (i == right) {
result.add(i - start + 1);
start = i + 1;
}
}
return result;
}
}class Solution {
public:
vector<int> partitionLabels(string s) {
unordered_map<char, int> last;
for (int i = 0; i < (int)s.size(); i++) last[s[i]] = i;
vector<int> result;
int start = 0, right = 0;
for (int i = 0; i < (int)s.size(); i++) {
right = max(right, last[s[i]]);
if (i == right) {
result.push_back(i - start + 1);
start = i + 1;
}
}
return result;
}
};func partitionLabels(s string) []int {
last := map[rune]int{}
for i, ch := range s {
last[ch] = i
}
result := []int{}
start, right := 0, 0
for i, ch := range s {
right = max(right, last[ch])
if i == right {
result = append(result, i-start+1)
start = i + 1
}
}
return result
}var partitionLabels = function(s) {
const last = new Map();
for (let i = 0; i < s.length; i++) last.set(s[i], i);
const result = [];
let start = 0, right = 0;
for (let i = 0; i < s.length; i++) {
right = Math.max(right, last.get(s[i]));
if (i === right) {
result.push(i - start + 1);
start = i + 1;
}
}
return result;
};function partitionLabels(s: string): number[] {
const last = new Map<string, number>();
for (let i = 0; i < s.length; i++) last.set(s[i], i);
const result: number[] = [];
let start = 0, right = 0;
for (let i = 0; i < s.length; i++) {
right = Math.max(right, last.get(s[i])!);
if (i === right) {
result.push(i - start + 1);
start = i + 1;
}
}
return result;
};