Partition Labels: Explaining the Greedy Last-Occurrence Trick in a Coding Interview
6 views
"Partition Labels" is a short problem that interviewers like because it rewards clear reasoning more than memorized code. You are given a string of lowercase letters and must split it into as many pieces as possible so that each letter appears in at most one piece. You return the sizes of those pieces. For "ababcbacadefegdehijhklij" the answer is [9, 7, 8].
Start with the observation, not the code
The key insight is simple to say out loud: once a piece contains a letter, that piece must extend at least to the last place the letter appears anywhere in the string. If the letter "a" shows up at index 0 and its last occurrence is index 8, the first piece cannot end before index 8. While scanning from 0 to 8 you may meet other letters whose last occurrence is even further right, so the boundary keeps moving outward. When your scan position finally equals the furthest boundary you have seen, every letter inside the current piece is finished, and you can safely cut.
Saying this before writing anything shows the interviewer that you understand why the algorithm works, which is usually worth more than a fast typing speed.
The algorithm in two passes
First pass: record the last index of every character in a small array of 26 integers or a dictionary.
Second pass: keep two variables, start and end. For each index i, set end to the maximum of end and last[s[i]]. If i equals end, append end - start + 1 to the result and set start to i + 1.
That is the entire solution. It runs in O(n) time and uses O(1) extra space, because the alphabet size is fixed at 26.
Why greedy is correct
Interviewers often follow up with "how do you know cutting as early as possible gives the maximum number of pieces?" A clean answer: any valid partition must place a cut only at positions where every letter seen so far has already had its last occurrence. Our scan cuts at exactly the first such position each time. Cutting later would merge pieces and reduce the count, and cutting earlier would break the rule. So the earliest legal cut is always optimal, and repeating that choice gives the best overall answer.
Common mistakes to mention
Candidates sometimes update end only when they see a new character, forgetting that a repeated character can still matter. Others compute piece sizes with off-by-one errors, so walk through the example by hand: the first cut happens at index 8, giving size 9. Testing a single-character string and a string where every letter is unique (each piece has size 1) are quick edge cases worth stating.
Connect it to related problems
This same "extend the boundary to the furthest reach" pattern appears in merge intervals and in jump-game style questions. Pointing out the connection signals pattern recognition, which many interviewers explicitly score.
Practicing the explanation, not just the answer
Most people can read this solution and nod along, but explaining it under pressure is different. During live practice or real technical interviews, tools such as Linkjob AI (https://linkjob.ai) can give real-time help, prompting you with the key observation or an edge case you forgot to test, so you keep talking through your reasoning instead of freezing. Combine that with a few timed mock sessions and Partition Labels becomes an easy chance to show calm, structured thinking.