Partition Labels

Intuition

A piece is only valid once it contains the last occurrence of every letter it holds. So the earliest we can possibly cut after position i is the maximum last-index among all characters seen so far. We walk left to right, continually pushing the candidate boundary outward to that maximum. The moment our scan index equals the boundary, nothing to the left needs anything to the right, so we can safely cut. Recording the width of each cut piece and restarting gives the greedy optimum, which also happens to be the largest number of pieces.

Algorithm walkthrough

1. 1Scan the string once and store, for every character, the index of its last appearance.
2. 2Initialize a partition start pointer and a running end pointer to 0.
3. 3For each index i, update the end pointer to the max of itself and the last index of s[i].
4. 4If i now equals the end pointer, the current window is self-contained: append (end - start + 1) to the answer.
5. 5Move the start pointer to i + 1 and continue scanning until the string is exhausted.
6. 6Return the collected list of piece lengths.

Implementation

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