LeetCode 763 · Greedy

Partition Labels, explained with a picture

Cutting a ribbon so every letter stays in one piece.

MediumGreedy
▶ Watch it step by step

The problem

Split a string into as many pieces as possible so that each letter appears in only one piece. Return the sizes of the pieces.

Input:  "ababcbacadefegdehijhklij"
Output: [9, 7, 8]

Picture it

Picture a ribbon of letters. First note where each letter appears for the last time. Walk along the ribbon, stretching the end of the current piece to the last appearance of every letter you pass. When your position reaches that end, every letter in the piece is finished, so you can cut there.

How to recognise it

  • You cut a string into pieces so that a letter never appears in two pieces, and you want as many pieces as possible.
  • Whichever piece holds the first copy of a letter must stretch to its last copy. That is a deadline, and deadlines can extend when you meet new letters inside the piece.
  • The input is lowercase letters, up to 500 characters, so the exact limits are gentle, but a single pass with a lookup table is the intended shape.
  • "Extend the current block to cover everything it forces, then cut" is the greedy interval-merging pattern.

Start with brute force

A cut between positions i − 1 and i is allowed exactly when the letters before the cut and the letters after it are disjoint. Test every cut position and use all the allowed ones.

def partition_brute(s):
    n = len(s)
    cuts = [0] + [i for i in range(1, n) if not (set(s[:i]) & set(s[i:]))] + [n]
    return [b - a for a, b in zip(cuts, cuts[1:])]

For each of the n − 1 cuts the two sets cost O(n) to build, so time is O(n²). That is fine for 500 characters (about 250,000 steps) but it does not scale, and the idea below is simpler to run. Space is O(n) for the sets.

From brute force to the idea

  1. Record deadlines. last[ch] is the index of the final copy of each letter. A piece containing ch must reach at least that index.
  2. Grow the current piece. Walk the string. For each position keep end = max(end, last[ch]): the farthest index the piece is forced to reach so far.
  3. Cut when the deadline is met. When i == end, every letter seen in this piece has its last copy at or before i, so nothing later belongs to this piece. Record the size end - start + 1.
  4. Start the next piece at i + 1.

Cutting as early as possible makes the pieces as small as possible, which gives the maximum number of pieces. Each cut is safe because no letter on the left appears on the right.

This is the key idea: extend the current piece to the last occurrence of every letter inside it, and cut the moment you reach that end.

The key idea

end = max(end, last[c]); cut when i == end. O(n).

Python solution

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    sizes, start, end = [], 0, 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])         # this piece must reach ch’s last copy
        if i == end:
            sizes.append(end - start + 1)  # safe to cut here
            start = i + 1
    return sizes

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): n − 1 cuts, each with two sets built in O(n)O(n): the sets
Last-index scan (shown code)O(n): one pass to build last, one pass to cutO(1): at most 26 letters in last (plus the list of sizes)

Edge cases

  • One letter ("a"): returns [1].
  • All the same ("aaaa"): returns [4]; one letter forces one piece.
  • All different ("abc"): returns [1, 1, 1].
  • Interleaved ("abab"): returns [4]; the last b forces the end.
  • Standard example "ababcbacadefegdehijhklij": returns [9, 7, 8].
  • A letter that spans nearly everything ("eccbbbbdec"): returns [10], because the first e has its last copy at the very end.
  • Empty string: returns []; the problem guarantees at least one letter.

Common mistakes

  • Forgetting start = i + 1, so later sizes are measured from the beginning: "abc" gives [1, 2, 3].
  • Using end = last[ch] instead of the maximum, which can shrink the deadline: "abab" returns [3, 1], and a letter appears in two pieces.
  • Building last from first occurrences instead of last ones.
  • Cutting when a letter's first copy ends, rather than when the whole piece's deadline is reached.
Your turn: list the pieces

Return the pieces themselves as strings instead of their sizes. For "ababcbacadefegdehijhklij" the answer is ["ababcbaca", "defegde", "hijhklij"]. Describe your approach, then write it if you like.

Compare with our answer

The same scan, but slice the string when you cut.

def partition_pieces(s):
    last = {ch: i for i, ch in enumerate(s)}
    pieces, start, end = [], 0, 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            pieces.append(s[start:end + 1])
            start = i + 1
    return pieces

partition_pieces("abab") is ["abab"] and partition_pieces("abc") is ["a", "b", "c"]. Time O(n), space O(n) for the output.

A strong answer mentions: the last dictionary, end as the maximum deadline, cutting at i == end, slicing s[start:end + 1], and moving start forward.

Check what stuck

1. You must split a log string into as many chunks as possible so that no event code appears in two chunks. Which approach fits best?

2. What does end represent in the shown code?

3. A learner deletes the line start = i + 1. For which input is the output now wrong?

Score 60% or more and the lesson is marked complete.