763.md

763. Partition Labels

Solution 1 (O(n))

class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        last = [0] * 26
        for i, ch in enumerate(S):
            last[ord(ch) - ord('a')] = i
        ans = []
        start = end = 0
        for i, ch in enumerate(S):
            end = max(end, last[ord(ch) - ord('a')])
            if i == end:
                ans.append(end - start + 1)
                start = end = i + 1
        return ans