Partition Labels
Split a string into as many parts as possible so each letter appears in only one part, by cutting when every letter seen has ended.
Problem Understanding
Partition Labels: split the string s into as many parts as possible so that each letter appears in at most one part, and return the sizes of the parts in order.
Example: "ababcbacadefegdehijhklij" returns [9, 7, 8]: ababcbaca, defegde, hijhklij.
The Intuition: A Part Must Reach Its Letters' Last Copies
If a part contains the letter a, it must also contain the last a in the string, or a would show up in two parts. So a part starting at start has to stretch at least to the last index of every letter inside it.
- Record
last[c]for every letter. - Scan with
end = max(end, last[s[i]]): each new letter may push the part further. - When
i == end, nothing in the part appears later. Cut here and start the next part ati + 1.
Cutting at the first moment it is allowed leaves the most room for later parts, which is why this greedy scan gives the maximum number of parts. It is merging intervals in disguise, with no sort needed.
Interactive Walkthrough
Below each letter is the index where it last appears. Watch end (outlined) jump right whenever a letter with a later last copy is scanned, and the part row fill in a whole block at each cut.
Dry Run Table
Input: "ababcbacadefegdehijhklij"
| Part | Letters | Stretched to | Size |
|---|---|---|---|
| 1 | a, b, c | 8 (last a) | 9 |
| 2 | d, e, f, g | 15 (last e) | 7 |
| 3 | h, i, j, k, l | 23 (last j) | 8 |
The answer is [9, 7, 8].
The Solution Template
Last indexes, then one scan that stretches and cuts.
Partition Labels Code
1var partitionLabels = function(s) {2 const last = {};3 for (let i = 0; i < s.length; i++) last[s[i]] = i;4 const sizes = [];5 let start = 0, end = 0;6 for (let i = 0; i < s.length; i++) {7 end = Math.max(end, last[s[i]]);8 if (i === end) {9 sizes.push(end - start + 1);10 start = i + 1;11 }12 }13 return sizes;14};
Edge Cases & Common Mistakes
- Every letter distinct: each character is its own part, all of size 1.
- A letter at both ends: the whole string is one part, as in
"eccbbbbdec". - Using the first occurrence: the part must reach the last copy of each letter, not the first.
- Returning the parts instead of sizes: the problem asks for lengths; compute
end − start + 1.
Summary
Record each letter's last index. Scan once, stretching end to the last copy of every letter met, and cut whenever i reaches end. Each cut is the earliest legal one, which maximises the parts. O(n) time, O(1) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet