763. 划分字母区间

https://leetcode-cn.com/problems/partition-labels/

解法一：贪心

先一次遍历S串，建立每个字符最后出现位置的hash。

然后再遍历一次S串，用[start : last]记录一个片段，start初始为0，last为S[0]最后出现的位置。i从start遍历到last，每次查hash，若出现比last还靠后的，更新last。遍历一轮后得到一个[start : last]片段，计入res。

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        res = []
        last_map = {}
        for i in range(len(S)):
            last_map[S[i]] = i
        start = 0
        while start < len(S):
            last = last_map[S[start]]
            i = start
            while i < last:
                if last_map[S[i]] > last:
                    last = last_map[S[i]]    #更新
                i += 1
            res.append(last-start+1)
            start = last+1
        return res