Partition Labels

main.md

Question

Approach

I first recorded the last occurrence of each character in the string. Then, I iterated through the string while maintaining a window that represents the current partition. For each character, I updated the right boundary of the window to the farthest last occurrence seen so far. Once I reached the end of this window, it meant that all characters in the window were unique to it—so I closed the partition, recorded its size, and started a new one.

Implementation

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {char: i for i, char in enumerate(s)}
        res = []
        start = end = 0

        for i, char in enumerate(s):
            end = max(end, last[char])
            if i == end:
                res.append(end - start + 1)
                start = i + 1

        return res

Complexities

• Time: O(n)
• Space: O(1)