Partition Labels — Solution

Problem

You are given a string and must split it into as many pieces as possible such that every letter appears in exactly one piece. The pieces must together cover the entire string (no gaps, no overlaps), and the order of characters must be preserved.

• Input: s = "ababcbacadefegdehijhklij"
• Output: [9, 7, 8]
• Explanation: The three parts are "ababcbaca", "defegde", and "hijhklij" — every letter belongs to exactly one part.

Counter-example: splitting "ababcbaca" into ["ab", "abcbaca"] is illegal because 'a' and 'b' appear in both halves.

Intuition

Every character forces its partition to extend at least as far as that character's last occurrence in the string. Scan left to right, continuously updating the farthest "last index" you've seen among all characters encountered so far. The moment your current position catches up to that farthest index, you've found a complete partition — every character you've seen ends before or at this point, so none of them can appear further right.

Solution — Greedy Last-Index Scan

Pre-record the last index of every character, then make a single left-to-right pass. Maintain a running partition_end that stretches as far right as any character in the current window demands. When the current index equals partition_end, the partition is sealed.

1. Build a map of each character to its rightmost position in the string.
2. Initialize partition_start = 0 and partition_end = 0.
3. For each index i, set partition_end = max(partition_end, last_index[s[i]]) to guarantee every occurrence of this character stays in the current partition.
4. When i == partition_end, record the partition size as partition_end - partition_start + 1, then advance partition_start to i + 1.
5. Repeat until the end of the string.

1def partitionLabels(s: str) -> list[int]:
2    last_index = {char: idx for idx, char in enumerate(s)}  # last occurrence of each character
3
4    result = []
5    partition_start = 0
6    partition_end = 0
7
8    for i, char in enumerate(s):
9        partition_end = max(partition_end, last_index[char])  # stretch end to cover all copies of this char
10        if i == partition_end:  # every char seen so far ends here — partition is complete
11            result.append(partition_end - partition_start + 1)
12            partition_start = partition_end + 1
13
14    return result

Time: O(n) — two linear passes: one to build the last-index map and one to scan.

Space: O(1) — the last-index map holds at most 26 entries regardless of string length.

Complexity Summary

Common Mistakes

• Not updating partition_end continuously: Checking only the first or current character's last index isn't enough — every character you encounter might push the boundary further right.
• Off-by-one on partition size: The size is partition_end - partition_start + 1, not partition_end - partition_start. Both endpoints are inclusive.
• Forgetting to reset partition_start: After recording a partition, partition_start must jump to partition_end + 1; leaving it at 0 causes all subsequent partitions to be measured from the beginning.
• Confusing first vs. last occurrence: The pre-computation must store the last index of each character, not the first. Using {char: idx} in a single forward pass naturally overwrites earlier positions with later ones.
• Thinking this is an interval-merge problem: It looks similar to merge-intervals, but here you don't start with a fixed list of intervals — you discover each character's interval on the fly as you scan.

Related Problems

• merge-intervals — also extends a running boundary as you process items, the core structural similarity
• non-overlapping-intervals — greedy interval selection where local decisions produce the global optimum
• jump-game — same "track the farthest reachable position" greedy pattern
• jump-game-ii — extends the reachability greedy to count minimum jumps, nearly identical scanning logic
• insert-interval — interval boundary reasoning and merging under a single-pass constraint