Partition Labels
Understanding the Problem
We need to split a string into the maximum number of parts where no letter appears in more than one part. Consider what that constraint means: if the letter 'a' appears at positions 0, 3, and 8, then all three of those positions must belong to the same partition. That partition must stretch at least from index 0 to index 8.
This leads to the core idea. Once we start a partition and encounter a character, we must extend the partition at least to the last occurrence of that character. Extending it may pull in new characters whose last occurrences push the boundary further out. The partition ends only when we reach a position where every character encountered so far has its last occurrence at or before the current position.
Key Constraints:
1 <= s.length <= 500→ An O(n^2) scan stays under 250,000 operations here, so even a brute-force approach runs fast. The greedy O(n) solution below is preferred because it removes the repeated work.sconsists of lowercase English letters → Only 26 possible characters, so a last-occurrence array of size 26 uses O(1) space.
Approach 1: Brute Force (Expand Partition Boundaries)
Intuition
Start a partition at index 0. Find where the first character last appears in the string; that index is the minimum end boundary. Scan every character between the start and that boundary. Each one may have a last occurrence further out, so extend the boundary whenever that happens. Once the scan reaches the boundary without extending it further, the partition is complete. Record its size and start the next partition.
This follows the same logic as the optimal solution, except it recomputes each last occurrence with a fresh scan instead of precomputing them once. That repeated work is what the next approach removes.
Algorithm
- Start with
partitionStart = 0. - Set
endto the last occurrence ofs[partitionStart](found by scanning the string from the right). - For each index
ifrompartitionStarttoend, find the last occurrence ofs[i]. If it is beyondend, updateend. - When
ireachesend, the partition is complete. Addend - partitionStart + 1to the result. - Set
partitionStart = end + 1and repeat until the string is fully partitioned.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). For each partition, we scan characters within the current window and for each one, we scan the string to find its last occurrence. With n up to 500, this is at most 250,000 operations.
- Space Complexity: O(1). We only use a few index variables. The output list does not count toward auxiliary space.
The last occurrence of each character never changes during the run, yet this approach recomputes it on every scan. Precomputing all 26 last occurrences once turns the repeated inner search into a single array lookup.
Approach 2: Greedy with Last Occurrence Map (Optimal)
Intuition
There are only 26 lowercase letters, so we can record where each character last appears in a single O(n) pass. With that map in hand, the partitioning becomes one greedy left-to-right scan.
Walk through the string maintaining the current partition's end boundary. For each character at position i, update end = max(end, lastOccurrence[char]). When i == end, every character seen so far in this partition has its last occurrence at or before position i, so no character from this partition appears later in the string and the cut is safe.
When i == end, every character in the range partitionStart to i has its last occurrence inside that range, since end is the maximum of all those last occurrences. None of them appears later, so cutting here keeps each letter within a single partition.
Cutting at the first valid i is also optimal. A shorter partition would leave some character's last occurrence outside it, breaking the containment rule, and any longer partition merges parts that could have been split, reducing the total count. So the earliest valid cut at each step maximizes the number of parts.
Algorithm
- Create an array
lastof size 26, wherelast[c]stores the last index of charactercin the string. - Fill
lastby scanning the string once from left to right. - Initialize
partitionStart = 0andend = 0. - Iterate through the string with index
i: - Update
end = max(end, last[s[i]]). - If
i == end, the current partition is complete. Addend - partitionStart + 1to the result. SetpartitionStart = i + 1. - Return the result list.
Visualization and Code
Loading animation...
- Time Complexity: O(n). One pass to build the last occurrence map and one pass to find partition boundaries. Total: O(2n) = O(n).
- Space Complexity: O(1). The last occurrence array has a fixed size of 26 regardless of input length. The output list does not count as auxiliary space.