Partition Labels

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}
    sizes, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Partition Labels. Given a string, cut it into as many parts as you can, so that each letter appears in only one part. Return the size of each part.

Take these twenty-four letters. A cut after the first four fails, because the letter A turns up again later. The best split is nine, seven and eight letters, and no letter crosses a cut.

The slow way tests every cut by scanning ahead for each letter on its left. That's a pass inside a pass: n squared.

Instead, first note where each letter appears last. A part that holds a letter must reach that letter's last spot, so plant a flag there, and push it further when a new letter reaches past it. When you reach the flag, cut. Cutting as early as possible gives the most parts: that's the greedy choice.

In code, a dictionary maps each letter to its last index. Walk the string, moving end to the larger of end and the letter's last index. When the index equals end, save the size and start the next part.

Let's run it. The first A sets the flag at eight, and B and C stay inside. Cut: nine. D pushes the flag to fourteen, then E to fifteen. Cut: seven. Then H, I and J push it to nineteen, twenty-two and twenty-three. Cut: eight.

Two passes over the string: linear time. The table holds at most twenty-six letters, so the space is constant.

Remember the last spot, push the flag, cut when you reach it. That's Partition Labels.