LC 763划分字母区间Partition Labels　中等

把字符串切成尽量多的片段，使每个字母只出现在一个片段里，返回各片段长度。

思路 先记录每个字母最后出现的位置，扫描时用 end 贪心扩展当前片段的最远边界，到达边界即切分。时间 O(n)。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}
        ans = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                ans.append(end - start + 1)
                start = i + 1
        return ans