Partition Labels: A Greedy Interview Problem You Can Prove in Two Sentences
Partition Labels asks you to split a string into as many parts as possible so that each letter appears in at most one part, and return the part sizes. It is a greedy problem, and the proof is short enough to say out loud.
Key observation
If a part contains a letter, it must extend at least to that letter's last occurrence. So first record last[c] for every character in one pass.
Greedy sweep
Walk the string keeping end, the furthest last occurrence seen in the current part. When the index reaches end, no letter inside the part appears later, so cut here and start a new part.
def partition_labels(s):
last = {c: i for i, c in enumerate(s)}
sizes, start, end = [], 0, 0
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
sizes.append(i - start + 1)
start = i + 1
return sizes
Time is O(n) and space is O(1) for a fixed alphabet (26 letters).
Why greedy is optimal
Every cut we make is forced to be no earlier, because end is the minimum valid boundary for the current part. And it is safe to cut there, because no character crosses it. Cutting at the earliest valid point each time maximises the number of parts. Two sentences, and the interviewer knows you are not guessing.
Related problems
Merge Intervals is the same idea in disguise: each letter defines an interval [first, last], and parts are the merged intervals. Mentioning this connection is a strong signal. Also related: Jump Game, where the reach variable plays the role of end.
Communicating it
Precompute, sweep, cut, and justify. If you would like a interview copilot app that prompts you to give the optimality argument during practice, we build one at Linkjob AI (disclosure: I am on the team).