Partition Labels
Split a string into the most parts so each letter appears in at most one part.
Open on LeetCode ↗Intuition
Cutting whenever a character changes fails because that character may reappear much later. Once a partition contains a character, it must extend through that character's final occurrence. While scanning, the farthest last occurrence of every character seen in the current partition defines the earliest safe boundary. Closing exactly at each safe boundary greedily maximizes the number of parts.
If each value must belong to only one segment, determine every value's full occurrence span. A greedy sweep can close a segment when all spans opened inside it have ended.
Approach
Record the final index of every character
Scan the string once and overwrite last[char] with its index. This lookup tells how far a partition must extend after including that character.
Grow the current required boundary
During a second scan, update end to the maximum of its current value and the current character's last index. New characters inside the range may push the boundary farther right.
Cut at the earliest safe position
When the scan index equals end, all characters in the current segment finish there or earlier. Append its length and begin the next segment after that index.
Solution
Common pitfalls
Cutting at the current character's last index only
end = last[char]
end = max(end, last[char])
An earlier character in the partition may require a later boundary.
Computing the wrong segment length
sizes.append(end - start)
sizes.append(end - start + 1)
Both boundary indices belong to the partition.
Starting the next segment at the boundary
start = end
start = end + 1
The boundary character was already included in the completed segment.
Edge cases
Every last occurrence equals its current index, producing one-character partitions.
Its last occurrence extends the first partition to the final index.
The running maximum absorbs every inner range before a cut is made.