Partition Labels
Partition Labels: split a string into the most parts so each letter appears in at most one part.
- 1 <= s.length <= 500
- s consists of lowercase English letters.
Intuition
Partition labels splits a string into as many pieces as possible so that each letter appears in only one piece. The instinct to cut whenever the character changes fails immediately, because a character can reappear far to the right — and if it does, both occurrences must land in the same part. That gives the governing constraint: - Once a partition contains a character, it must extend at least as far as that character's final occurrence in the whole string. So the last occurrence of every character is exactly the information needed, and one preliminary pass collects it. Then scan again, maintaining the boundary the current partition is obliged to reach. Each character encountered may push that boundary further right — never left, since the boundary is a maximum. When the scan position finally equals the boundary, every character seen in this segment has been fully consumed, and cutting here is safe. Cutting at the earliest safe position is what maximises the number of parts. Extending any further would merge two independent segments and produce fewer pieces, while cutting earlier would split a character across two parts and be invalid. The earliest safe cut is therefore both legal and optimal, which is why the greedy rule needs no backtracking.
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
Before reading on: price up what enumerating every case costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n) time and O(1) space.
Record each character's last index
Scan the string once, overwriting last[char] with the current index each time. This single pass supplies the only lookup the algorithm needs — how far a partition must stretch once it contains a given character.
Track the boundary the segment must reach
During the second scan, keep an end value. For every character, set end = max(end, last[char]). New characters inside the segment can only push it further right, never pull it back.
Cut when the index reaches the boundary
When the scan position equals end, every character in this segment has its final occurrence at or before here. Record the segment length and start the next one at the following index.
Understand why the earliest cut is optimal
Cutting sooner would split a character across two parts and be invalid; cutting later would merge two independent segments and yield fewer pieces. The earliest safe cut is therefore both legal and maximal — no backtracking is ever needed.
Return lengths, not the substrings
The problem asks for the size of each part, so append end - start + 1 and set start = end + 1. Building the actual substrings is extra work the answer does not require.
Cost of the two passes
Two linear scans over the string give O(n) time, and the last-occurrence map is bounded by the alphabet size, so space is O(1) for lowercase input — 26 entries regardless of string length.
Solution & live demo
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.