Partition Labels

Partition Labels is a clean greedy problem that hides a hash-map trick. It teaches you to think about a character's reach — the farthest place it still appears — and to grow a window until nothing inside it escapes.

The slow way first

You could try every possible set of cut points and check that no letter straddles a cut. There are exponentially many ways to place cuts, so that is hopeless. Even a smarter check — for each candidate cut, scan both sides for a shared letter — is O(n²) and fiddly.

The question to ask: when is it safe to close a piece? A piece can end at position i only if every letter inside it has already had its last occurrence at or before i. So the real thing I need to know about each letter is: where does it appear for the last time?

The idea: extend to the farthest last-index

First, record the last index of every character (one pass, a hash map). Then sweep left to right keeping a running end for the current piece. At each character c, push end out to max(end, last[c]). When i finally equals end, no letter in the current piece reaches past i, so we cut here and start a fresh piece.

The key insight: end is the farthest reach of any letter seen so far in this piece. The first index where i catches end is the earliest legal cut — which gives the most pieces possible.

Walk through it

Step through the animation. The i pointer scans left to right and the end pointer marks how far the current piece must stretch. Watch the second piece: when i hits e, its last occurrence at index 15 drags end outward, delaying the cut. Each time i meets end, the finished piece locks in and its length is recorded.

Pseudocode

last = last index of each character in s     # one pass, a map
result = empty list
start = end = 0
for each index i with character c in s:
    end = max(end, last[c])                  # stretch the piece to c's reach
    if i == end:                             # nothing inside reaches past i
        record (end - start + 1)             # size of this piece
        start = i + 1                         # next piece begins after the cut
return result

The Python solution

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}
    result = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        # keep extending until i catches the end
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    return result

• last maps each character to the last index where it appears — built in one pass with a dict comprehension.
• start and end bound the current piece; end is the farthest reach of any letter seen so far.
• Line 6 is the heart of the greedy: end = max(end, last[c]) stretches the piece so the current letter stays inside it.
• if i == end is the cut condition — when the scan catches up to the farthest reach, the piece is complete.
• We record end - start + 1 (the length), then move start just past the cut for the next piece.

Complexity

Both passes are linear, so the whole thing is O(n). The map holds at most 26 entries (one per lowercase letter), so the extra space is constant — O(1).

When this pattern shows up

Practice