Partition Labels

Every letter draws an invisible span across the string. Valid cuts can only live between those spans.

Merge character spans

An interval is the span from one position through another, including both ends. Find each letter's first and last position. Sort those intervals by their first position, then merge overlaps. Every merged interval is one forced part: splitting inside it would place some letter on both sides.

def partition_labels(s: str) -> list[int]:
    first: dict[str, int] = {}
    last: dict[str, int] = {}
    for i, letter in enumerate(s):
        if letter not in first:
            first[letter] = i
        last[letter] = i
 
    spans = sorted((first[letter], last[letter]) for letter in first)
    part_start, part_end = spans[0]
    sizes: list[int] = []
 
    for span_start, span_end in spans[1:]:
        if span_start > part_end:
            sizes.append(part_end - part_start + 1)
            part_start, part_end = span_start, span_end
        else:
            part_end = max(part_end, span_end)
    sizes.append(part_end - part_start + 1)
    return sizes

Time O(n) — scanning dominates because there are at most 26 spans to sort. Space O(1) — the alphabet bounds the maps and span list to 26 entries.

Last-occurrence sweep

You don't need to build the intervals explicitly. Record only each letter's last index, then sweep left to right. part_end is the furthest last occurrence belonging to the current part. When the scan reaches it, the part is closed and safe to emit.

def partition_labels(s: str) -> list[int]:
    last = {letter: i for i, letter in enumerate(s)}
    sizes: list[int] = []
    part_start = 0
    part_end = 0
 
    for i, letter in enumerate(s):
        part_end = max(part_end, last[letter])
        if i == part_end:
            sizes.append(part_end - part_start + 1)
            part_start = i + 1
    return sizes

The exchange argument is a proof that replacing another valid choice with the greedy choice can't make the final result worse. Once a part starts, every letter encountered forces its last occurrence into that part, so no valid first cut can come before part_end. When the scan reaches part_end, cutting there is safe. Exchange any later first cut in an optimal partition for this earliest safe cut: the first part gets no invalid split, and the untouched suffix has at least as many chances to be partitioned. Making that earliest safe cut repeatedly is therefore globally optimal for maximizing the number of parts.

Time O(n) — one pass records last positions and one pass forms parts. Space O(1) because at most 26 last positions are stored.