LC763　划分字母区间¶

中等通过率 79%python3核心代码模式贪心算法样例通过牛客 AC贪心哈希表双指针字符串

讲解章节：贪心

一句话

先记下每个字母最后出现的位置，再扫一遍，边扫边把片段右界推到够远为止。

解题思路¶

这题考什么¶

约束只有一条：同一个字母不能跨片段。把它翻译成下标的语言——

若片段从 start 开始，且它包含字母 c 的某次出现，
那么 c 的**最后一次**出现也必须落在这个片段里，
于是片段的右端至少要到 last[c]。

所以片段的右端由「段内出现过的所有字母的 last 值的最大者」顶着。从 start 往右扫，每见到一个字母就把右界 end 抬到 max(end, last[c])；当扫描位置 i 追上 end，说明段内每个字母的最后一次出现都已被囊括，这里可以切一刀。

片段数要尽可能多，等价于每一刀都切在最早可切的位置。这条贪心的论据是：任何一种合法划分的第一刀都不可能早于上面算出的 end——切早了必然有某个字母被劈成两段。所以本题解切出的第一个片段是所有合法划分里最短的那个，剩下的后缀也就最长，可切的机会最多；对后缀递归地重复同样的论证，得到的片段数不少于任何其它划分。这正是贪心的「交换论证」形态，见贪心的 47.2 节。

还有一点让这题成立却容易被略过：最早可切的位置切下去之后， 剩下的后缀不会被前面的选择污染——因为切点右边不会再出现段内的任何字母（它们的最后一次出现都在切点左边）。子问题与原问题同形，贪心才能一路做下去。

第一遍扫描求 last 是不可省的：正着扫的时候无法知道一个字母后面还会不会再出现。直接用「字母 -> 下标」的字典覆盖写入即可，最后留下的自然是最后一次出现的位置。

数据规模与复杂度¶

1 <= s.length <= 500，s 只含小写英文字母，所以字母种类至多 26。时间 O(n + 字母种类数)：两趟扫描；空间 O(字母种类数) = O(26) = O(1)，与 n 无关。 n 只有 500，即使对每个起点重新扫一遍求 end（O(n^2) = 2.5e5）也跑得动，但两趟线性扫既更短也更容易说清楚。

坑在哪¶

必须扫两遍。只扫一遍、边走边判「这个字母后面还出现吗」需要往后看，那就退化成每个位置再扫一次的 O(n^2)。先把 last 表建好，第二遍才能 O(1) 地问出答案。
end 要在片段内部持续抬高，不是只看片段的第一个字母。 s = "abab" 是最小的反例：首字母 a 的 last 是 2，只认它就会在 i = 2 处切，切成 "aba" 与 "b"，字母 b 被劈成两段，划分根本不合法（正确答案是 [4]）。样例 1 的第二段 "defegde" 同理——开头的 d 的 last 是 14，是中途的 e 把右界顶到 15 的。
切点判断用 i == end。写成 i >= end 在本题等价（end 只会被抬高、且 last[c] >= i 保证 end 永远不小于 i），但写 i == end 更贴合「扫描位置追上右界」这个含义。
片段长度是 end - start + 1，闭区间两端都算，减一或加错就整体差 1。切完之后 start 要更新成 i + 1，即下一个字符；写成 i 会让相邻片段重叠一个字符，长度全部多 1，且总和不等于 n。
返回的是每个片段的长度列表，不是切点下标，也不是子串。判题严格比对结构，形状不对直接不过。
本题走严格比对，产出顺序必须与原串的先后一致。片段本身是唯一确定的（最早可切的位置唯一），所以只要从左往右扫就自然对齐，不存在多解。
end 初值取 0 是安全的：第一次进循环时 i = 0，last[s[0]] >= 0， end 立刻被抬到该有的位置。start 初值取 0 表示第一个片段从头开始。

样例复核¶

s = "ababcbacadefegdehijhklij"，长度 24。 last 表里 a -> 8、b -> 5、c -> 7、d -> 14、e -> 15、f -> 11、g -> 13、 h -> 19、i -> 22、j -> 23、k -> 20、l -> 21。

i=0 是 a，end 抬到 8；中途 b/c 的 last 是 5 和 7，都不超过 8；
i=8 追上 end，切出 [0, 8]，长度 9，start = 9。
i=9 是 d，end 抬到 14；e 把 end 抬到 15；f、g 的 last 是 11、13，不改；
i=15 追上 end，切出 [9, 15]，长度 7，start = 16。
i=16 是 h，end 抬到 19；i、j 把 end 抬到 22、23；k、l 不改；
i=23 追上 end，切出 [16, 23]，长度 8。

返回 [9, 7, 8]，与样例一致。 s = "eccbbbbdec"：e 的 last 是 8、c 的是 9，第一个字符就把 end 顶到 8，随后 c 把它顶到 9，直到 i=9 才切，返回 [10]，与样例一致。

参考实现¶

solutions/leetcode/LC763/sol.py
from typing import List, Optional


class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 第一遍：记下每个字母最后一次出现的下标。同一个字母重复写入时后写的覆盖先写的，
        # 扫完留下的自然就是最后一次的位置。正着扫时无法预知后面还有没有该字母，
        # 所以这一遍不能省
        last = {}
        for i, ch in enumerate(s):
            last[ch] = i
        res = []
        # start 是当前片段的左端（闭区间），end 是当前片段右端的下界，
        # 随着段内见到的字母不断被抬高
        start = 0
        end = 0
        # 第二遍：边扫边抬右界，追上就切
        for i, ch in enumerate(s):
            # 段内出现过 ch，那么 ch 的最后一次出现也必须留在本段，右界至少到 last[ch]。
            # 只看片段首字母是不够的，中途的字母同样可能把右界顶得更远
            if last[ch] > end:
                end = last[ch]
            # 扫描位置追上右界：段内每个字母的最后一次出现都已被囊括，可以切。
            # 切在最早可切的位置，片段数才最多
            if i == end:
                # 闭区间 [start, end] 的长度是 end - start + 1，两端都算在内
                res.append(end - start + 1)
                # 下一段从切点的**下一个**字符开始；写成 i 会让相邻片段重叠一个字符
                start = i + 1
        return res

LC763 划分字母区间¶