4.26.7 — Partition Labels

LeetCode 763 · Medium

The problem

Split the string into as many parts as possible, so that each letter appears in at most one part. Return the sizes of the parts.

s = "ababcbacadefegdehijhklij"   →  [9,7,8]
    "ababcbaca" | "defegde" | "hijhklij"

The pattern

A part cannot end before the last occurrence of every letter it contains. So:

Precompute the last index of each letter. Then sweep, extending the current part's end to cover every letter you meet, and cut as soon as you reach that end.

Two passes. The first builds a 26-entry table; the second is one linear sweep.

Why this is optimal. The part must extend at least to the furthest last-occurrence of anything inside it, so cutting earlier is impossible. And cutting the moment you can is what maximises the number of parts. There is no choice — the boundary is forced, exactly like 4.26.5 Hand of Straights.

The solution

Python

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c: i for i, c in enumerate(s)}       # last index of each letter

        result = []
        start = end = 0

        for i, c in enumerate(s):
            end = max(end, last[c])                  # this part must reach here

            if i == end:                             # nothing inside reaches further
                result.append(end - start + 1)
                start = i + 1

        return result

TypeScript

function partitionLabels(s: string): number[] {
  const last = new Map<string, number>();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);

  const result: number[] = [];
  let start = 0, end = 0;

  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i])!);

    if (i === end) {
      result.push(end - start + 1);
      start = i + 1;
    }
  }

  return result;
}

{c: i for i, c in enumerate(s)} keeps the last index of each letter, because later assignments overwrite earlier ones. That one-liner is the whole precomputation, and it is worth noticing that a dictionary comprehension naturally keeps the last value.

end = max(end, last[c]) is the extension. Every letter you meet drags the boundary out to wherever that letter last appears.

i == end is the cut. You have walked to the furthest point anything in this part requires, so nothing inside it appears later. Cut here.

end - start + 1 is the part's length, with the +1 because both ends are included.

Trace

"ababcbacadefegdehijhklij"

Last occurrences: a at 8, b at 5, c at 7, d at 14, e at 15, f at 11, g at 13, h at 19, i at 22, j at 23, k at 20, l at 21.

i	char	end after	cut?
0	a	8	no
1	b	8	no
4	c	8	no
8	a	8	yes → part of length 9
9	d	14	no
11	f	14	no
13	g	15 (from e at 11)	no
15	e	15	yes → length 7
16…	h i j k l	23	cut at 23 → length 8

[9, 7, 8] ✓.

Complexity

O(n) time — two passes. O(1) space, since the table holds at most 26 letters.

This is an interval problem in disguise

Each letter defines an interval from its first to its last occurrence. Two letters must be in the same part exactly when their intervals overlap. So the parts are the connected groups of overlapping intervals — which is Merge Intervals (4.27.2).

The sweep above is merging those intervals without ever building them, because walking the string visits them in order of their start already.

Saying this out loud is the strongest thing you can do on this problem. It shows you see the structure rather than the trick, and it is why this problem sits between the greedy and interval chapters.

Where this goes next

• Merge Intervals — the same merging, stated explicitly. 4.27.2.
• Jump Game II — the same "extend the reach, then cut at the boundary" sweep. 4.26.3. These two problems have near-identical code and completely different stories, which is worth noticing once.
• Video Stitching, Minimum Taps — interval covering with the same reach-extension loop.

What the interviewer will push on

"Why must a part reach the last occurrence of every letter inside it?" Otherwise that letter appears in two parts.

"Why is cutting as early as possible optimal?" The boundary is forced, and cutting at the first legal point maximises the count.

"How do you get the last occurrences?" One pass, letting later writes overwrite earlier ones.

"What is the space complexity?" O(1) — 26 letters, fixed. Say why it is constant rather than O(n).

"Is this related to any other problem?" Merge Intervals, with one interval per letter.

One thing to volunteer: the interval framing, and the fact that this is Jump Game II's loop with a different meaning. Two connections in one sentence each, and both show the pattern rather than the puzzle.

Next: 4.26.8 Valid Parenthesis String — the last greedy, where you track a range of possibilities instead of one number.