763. 划分字母区间

763. 划分字母区间

中等

提示

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

📝 核心笔记：划分字母区间 (Partition Labels)

1. 核心思想 (一句话总结)

“橡皮筋扩容法：先用雷达扫描一遍记录每个字母的‘最终归宿’；然后再走一遍，遇到谁就把当前区间的边界‘撑’大到它的归宿位置，直到走到边界为止，咔嚓一刀。”

• 预处理：必须先知道每个字母最后出现在哪 (last[])。
• 贪心扩充：遍历字符时，当前片段的结束点 end 必须能够覆盖当前字符的 last 位置。
• 切割时机：当遍历指针 i 追上了扩充后的边界 end，说明当前片段里的所有字符都已处理完毕，可以安全切割。

2. 算法流程 (Greedy Scan)

• • 遍历字符串，用数组 last[26] 记录每个字母最后一次出现的下标。
  • 例如 abca，a 的 last 是 3。

• • 维护两个指针：start (当前片段起点) 和 end (当前片段预估的终点)。
  • 遍历字符串 i 从 0 到 n-1。

• • 对于字符 s[i]，查找它的 last 位置。
  • end = Math.max(end, last[s[i]])。如果这个字符最后出现在很后面，边界就被迫撑大了。

• • 如果 i == end，说明我们终于走到了目前所需的最远边界。
  • 记录长度 end – start + 1。
  • 重置起点 start = i + 1。

🔍 代码回忆清单

// 题目：LC 763. Partition Labels
class Solution {
public List<Integer> partitionLabels(String S) {
char[] s = S.toCharArray(); // 转数组提速
int n = s.length;

// 1. 预处理：记录每个字母最后出现的下标
// 就像记录每个人的"离场时间"
int[] last = new int[26];
for (int i = 0; i < n; i++) {
last[s[i] – 'a'] = i;
}

List<Integer> ans = new ArrayList<>();
int start = 0; // 当前片段起点
int end = 0; // 当前片段最远能延伸到的地方

// 2. 二次遍历：贪心切分
for (int i = 0; i < n; i++) {
// 3. 扩充边界
// 只要当前字符的"离场时间"比 end 晚，我们就得被迫延长时间
end = Math.max(end, last[s[i] – 'a']);

// 4. 到达边界
// 当前位置 i 追上了 end，说明这一段里的所有人都离场了
if (end == i) {
ans.add(end – start + 1); // 记录长度
start = i + 1; // 准备开启下一段
}
}
return ans;
}
}

⚡ 快速复习 CheckList (易错点)

• [ ] 为什么是 end == i 而不是 end == last[s[i]]？

• • 因为 end 是当前片段内所有字符的 last 值的最大值。
  • 可能 s[i] 的 last 很早就在前面结束了，但前面某个字符把 end 撑到了后面。必须等到指针 i 真正走到那个最远的 end，才能保证片段完整。

• [ ] start 的更新逻辑？

• • 切割后，下一段的起点自然是 i + 1。
  • 计算长度公式：end – start + 1 (闭区间长度)。

• [ ] 时间复杂度？

• • $O(N)$。字符串被扫描了两次（一次记 last，一次切分）。
  • 空间复杂度 $O(1)$ (固定 26 大小的数组)。

🖼️ 数字演练

S = "abaccc"

last 数组: a->2, b->1, c->5

• • last['a'] = 2.
  • end = max(0, 2) = 2. (边界撑到 2)
  • i(0) != end(2), 继续。

• • last['b'] = 1.
  • end = max(2, 1) = 2. (边界保持 2)
  • i(1) != end(2), 继续。

• • last['a'] = 2.
  • end = max(2, 2) = 2.
  • i(2) == end(2)! 切割！
  • 长度 2 – 0 + 1 = 3 ("aba"). start 变为 3.

• • last['c'] = 5.
  • end = max(0, 5) = 5. (边界撑到 5)
  • i(3) != end(5).

• • end 始终维持 5。
  • 当 i=5 时，i(5) == end(5)。切割！
  • 长度 5 – 3 + 1 = 3 ("ccc").

最终结果: [3, 3]。