Last-occurrence partition

44 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Cut the string ababcbacadefegde into as many pieces as possible so that no letter appears in two different pieces. By hand you would start a piece at the first a, notice that a appears again later, scan forward to its last appearance, notice that the piece now contains b and c, check where those last appear, and so on. It works, but every time a new letter enters the piece you rescan the string to find its last position, and with a long string of many letters that is a lot of rescanning: O(n) per letter, up to O(n × 26) checks for each piece and more in careless versions.

Build the structure, one piece at a time

The first piece of structure is a tiny table: for each letter, the index of its last occurrence. One pass over the string fills it, overwriting as it goes. For our string: a → 8, b → 5, c → 7, d → 14, e → 15, f → 11, g → 13.

The second piece is one number, end: the furthest index the current piece must stretch to. Walk the string a second time. At each index i, set end = max(end, last[s[i]]). When i catches up with end, the piece can close here: every letter inside it has its last occurrence at or before end.

Pieces of length 9 and 7. The piece could not be cut at 8 + 8 because d and e would be split across the cut.

Why it is correct

The invariant: while scanning the current piece, end is the maximum last-occurrence of every letter seen in the piece so far. A piece cannot close before end, because some letter in it reappears at end. When i reaches end, every letter in the piece has its last occurrence at or before i (that is what the maximum says), so none of them appears later, and closing here is legal. Closing as early as legal makes the most pieces: any cut earlier than this one would split some letter, and delaying the cut only merges pieces that could have been separate.

end = max over j ≤ i in the piece of last[s[j]]; close when i = end

Why it is fast

Two passes over the string, each doing constant work per character, plus a table of 26 integers: O(n) time and O(1) extra memory. The precomputed table is what removes the rescanning; "where does this letter last appear" becomes a lookup.

How to recognise it in an interview

Cues: "partition into as many parts as possible", "each letter in at most one part", or intervals defined by first and last occurrence. Say: I will precompute each element's last position, then sweep with a running furthest-reach and cut when the index meets it. Partition Labels is the example. Max Chunks To Make Sorted is the same sweep where the reach is the maximum value seen so far compared with the index. Merge Intervals uses the identical "extend the current end, close when passed" motion over sorted intervals.

02The idea in one line

Extend the current chunk to the last occurrence of every char inside it.

Reach for it when: Partition labels, max chunks to make sorted, merge intervals by reach.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Partition Labels on 'ababcbacadefegde'. These are its captions in order, so you can follow without the video or check a step you missed.

1. Precompute each letter's last index; a part cannot close before them
2. 'a' last appears at 8: end stretches to 8
3. 'b' last at 5 ≤ 8: end stays
4. 'a' last at 8 ≤ 8: end stays
5. 'b' last at 5 ≤ 8: end stays
6. 'c' last at 7 ≤ 8: end stays
7. 'b' last at 5 ≤ 8: end stays
8. 'a' last at 8 ≤ 8: end stays
9. 'c' last at 7 ≤ 8: end stays
10. i = end = 8: close a part of size 9
11. 'd' last appears at 14: end stretches to 14
12. 'e' last appears at 15: end stretches to 15
13. 'f' last at 11 ≤ 15: end stays
14. 'e' last at 15 ≤ 15: end stays
15. 'g' last at 13 ≤ 15: end stays
16. 'd' last at 14 ≤ 15: end stays
17. i = end = 15: close a part of size 7
18. Parts: 9, 7 (not 8 + 8: the 'd' and 'e' would be split)
19. Two passes over the string: O(n) time, 26 counters

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Greedy: Furthest reach (jump game), Sort, then take greedily, Reset-on-negative sweep, Two-pass neighbour constraints, Counting-based greedy (small alphabet), Two-pointer assignment after sorting.