Partition Labels

Intuition

Solution

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        start = {}
        end = {}
        for i, c in enumerate(S):
            if c not in start:
                start[c] = i
            end[c] = i

        ans = []
        using = set()
        l = 0
        for i, c in enumerate(S):
            l += 1
            if start[c] == i:
                using.add(c)
            if end[c] == i:
                using.remove(c)
            if not using:
                ans.append(l)
                l = 0
        return ans