LeetCode 763.划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        max_index = {item: idx for idx, item in enumerate(S)}  # 这样写就是一个键：一个值，然后通过遍历来更新到最大的那个index
        #print(max_index)
        start, end = 0, 0  # 起始边界， 结束边界
        ans = []        
        for idx, i in enumerate(S):
            end = max(end, max_index[i])   # 这里就是用边界和当前遍历到的那个字母的最大index去比较，看看谁大，
                                           # 如果最大index大就扩充边界。
            if idx == end:  # 最后，遍历的位置和边界重合了，那就ok了，从这里截断并记录长度。 就这些，可以再慢慢理解下。
                ans.append(end - start + 1)
                start = idx + 1
        
        return ans