leetcode763. Partition Labels

原题链接https://leetcode.com/problems/partition-labels/

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

统计出每一个字母最右的索引，储存在字典中，每个字符块的最后一位一定是所在字母的最右位置。那么一个字符块中，所有字符的索引包括其对应的最右位置索引，也小于最后一位的索引值。
遍历字符串，赋值end为当前字母的最右位置索引，不断更新end，直至end与遍历索引i相等，此时所有索引小于i的值都被遍历过了，而且其最右索引值也小于当前的end=i,故而第一块字符块找到了。

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