LeetCode 763. 划分字母区间

2026-01-13 HGNULB 约 5 分钟

文章信息 11 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 20-50 字节跳动美团阿里巴巴京东华为 LeetCode 热题 100

题目描述

✅ 763. 划分字母区间

题意分析

要把字符串切成若干连续且不重叠的片段，切完后拼起来仍是原串，同时满足「同一个字母不能跨片段出现」，在所有满足条件的切法里选片段数最多的那一种，返回各片段的长度。
约束给的信号很干净：字符串只含 26 个小写字母，长度 500 量级。字符集固定意味着「每个字母的信息」可以用一个长度 26 的数组存下，$O(1)$ 空间；长度不大则说明 $O(n^2)$ 也能过，但显然存在更直接的线性做法。
边界要想到三种：整串可能一段都切不开，比如 "abac" 只能整体作为一段；每个字母都只出现一次时可以切成 $n$ 段；答案里所有长度之和必然等于串长，这是一个很好用的自检条件。

解法：记录最后位置后贪心切分

核心思路

每个字母只能出现在一个片段中。只要当前片段包含字母 c，片段右端就至少要覆盖 c 的最后出现位置；至于中间出现了几次并不重要。因此先预处理每个字母的最后下标，再从左到右确定片段边界。

扫描当前片段时维护 end，它表示已读字符要求覆盖到的最远位置。处理到 i 后始终有：

end = max(last[s[k]])，start <= k <= i

这条不变量说明：i < end 时不能切，因为当前片段中至少有一个字母还会在后面出现；i == end 时可以切，因为片段内所有字母都已在此处或此前最后一次出现。

为什么此时立刻切最优？i == end 是当前片段最早的合法右端点。把切点继续向右推只会合并本可独立的后缀，不可能增加片段数，所以选择最早合法切点能得到最多片段。

解题步骤

扫描字符串，用长度为 26 的数组 last 记录每个字母最后一次出现的下标。

用 start 表示当前片段起点，用 end 表示当前片段必须覆盖的最远位置。

再次从左到右扫描，令 end = max(end, last[s[i]])。

当 i == end 时，记录当前片段长度 end - start + 1，再令 start = i + 1。

扫描结束后，所有片段长度之和应等于原字符串长度。

以 "ababcbacadefegdehijhklij" 为例：首字符 a 把第一段右端定到 8，中途遇到的 b、c 都没有把它推得更远，于是在 8 切出长度 9；第二段的边界由 d 的 14 扩到 e 的 15，切出长度 7；第三段最终被 j 扩到 23，切出长度 8，答案为 [9, 7, 8]。

代码实现

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 个小写字母；返回结果不计入额外空间。

关键点总结

将“同一字母不能跨片段”转化为“片段必须覆盖该字母的最后出现位置”。

end 不是某一个字母的末位置，而是当前片段内所有字母末位置的最大值。

i == end 同时给出合法性与最优性：此处能切，并且是最早能切的位置。

面试时应能明确说出不变量，并用“推迟切点不会增加段数”解释贪心正确性。

易错点总结

预处理必须记录最后出现位置，而不是第一次出现位置或出现次数。

更新右端点必须取 max；直接赋值会让边界回退。例如 "abac" 中看到 b 时不能把边界从 2 改回 1。

不能只判断当前字符是否最后一次出现，还要满足当前片段内所有字符的约束。例如 "abba" 只能整体成段。

片段长度是 end - start + 1，切分后要把 start 更新为 i + 1。

不要边统计最后位置边切分；未来位置尚未知时会过早切开 "abac"。

相似题目

题目	难度	考察点
45. 跳跃游戏 II	中等	同样维护最远可达边界，但求到达终点的最少步数
55. 跳跃游戏	中等	单调扩张边界，判断能否覆盖到末尾
56. 合并区间	中等	区间由输入直接给出，需先排序再合并重叠
57. 插入区间	中等	在已有序区间中插入新区间并局部合并
228. 汇总区间	简单	按数值连续性切段，边界条件来自相邻差值
435. 无重叠区间	中等	按右端点排序贪心，求最少删除数
452. 用最少数量的箭引爆气球	中等	求最少的公共交点数，与本题的最多段数互为对偶