Split the string into as many parts as possible, so that each letter appears in at most one part. Return the sizes of the parts.
Restating the Problem: You have a string of lowercase English letters. You want to chop it into contiguous substrings (partitions). The rule is: if a letter (like 'a') appears in one partition, all other 'a's in the string must also be in that exact same partition. You want to make as many partitions as possible.
Constraints to note: The string length is up to 500, which is small, but an O(n) solution is straightforward and expected. The string contains only lowercase English letters, meaning we have a fixed alphabet size of 26.
s = "ababcbacadefegdehijhklij" → [9,7,8] "ababcbaca" | "defegde" | "hijhklij"
You could try all possible partitions. For a string of length n, there are n-1 places to put a cut, meaning 2^{n-1} possible ways to partition the string. For each partitioning, you'd check if any letter crosses boundaries. This O(2^n) approach is incredibly slow and completely unnecessary.
A part cannot end before the last occurrence of every letter it contains. So:
Precompute the last index of each letter. Then sweep, extending the current part's end to cover every letter you meet, and cut as soon as you reach that end.
Two passes. The first builds a 26-entry table; the second is one linear sweep.
Why this is optimal. The part must extend at least to the furthest last-occurrence of anything inside it, so cutting earlier is impossible. And cutting the moment you can is what maximises the number of parts. There is no choice — the boundary is forced, exactly like 4.26.5 Hand of Straights.
class Solution: def partitionLabels(self, s: str) -> List[int]: last = {c: i for i, c in enumerate(s)} # (1) last index of each letter result = [] # (2) start = end = 0 # (3) for i, c in enumerate(s): # (4) end = max(end, last[c]) # (5) this part must reach here if i == end: # (6) nothing inside reaches further result.append(end - start + 1) # (7) start = i + 1 # (8) return result
ts
function partitionLabels(s: string): number[] { const last = new Map<string, number>(); // (1) for (let i = 0; i < s.length; i++) last.set(s[i], i); const result: number[] = []; // (2) let start = 0, end = 0; // (3) for (let i = 0; i < s.length; i++) { // (4) end = Math.max(end, last.get(s[i])!); // (5) if (i === end) { // (6) result.push(end - start + 1); // (7) start = i + 1; // (8) } } return result;}
(1) The last position of every letter in the string. Every copy of a letter must be in the same part, so a part containing a letter must stretch at least to that letter's last position.
(2) The sizes of the parts.
(3) The current part starts at start, and must stretch at least to end.
(4) Walk the string.
(5) This letter's last copy is at last[c], so the part must reach at least there.
(6) We have reached the furthest point any letter in this part needs. No letter seen so far appears again later, so the part can end here.
(7) Record its size, and
(8) start the next part at the next position.
{c: i for i, c in enumerate(s)} keeps the last index of each letter, because later assignments overwrite earlier ones. That one line is the whole precomputation. A dictionary built this way naturally keeps the last value for each key.
end = max(end, last[c]) is the extension. Every letter you meet drags the boundary out to wherever that letter last appears.
i == end is the cut. You have walked to the furthest point anything in this part requires, so nothing inside it appears later. Cut here.
Code Walkthrough:
Precomputation: We first iterate through the string to build a dictionary/map last that records the final index where each character appears.
Initialization: We set start = 0 and end = 0 to track the boundaries of our current partition.
Iterating for Cuts: We loop through the string again with index i.
Extending the Boundary: At each character c, we check last[c]. If this character appears later in the string than our current end, we must extend end to last[c].
Making a Cut: If our current index i catches up to end (i == end), it means we've passed the last occurrence of every character we've seen so far in this partition. We can safely make a cut. We record the size end - start + 1 and begin a new partition at start = i + 1.
end - start + 1 is the part's length, with the +1 because both ends are included.
O(n) time — two passes. O(1) space, since the table holds at most 26 letters.
Time Complexity:O(n). We pass through the string of length n exactly twice: once to find the last occurrences and once to determine the partitions.
Space Complexity:O(1). The hash map stores at most 26 key-value pairs (one for each lowercase English letter), which uses a constant amount of extra memory.
Each letter defines an interval from its first to its last occurrence. Two letters must be in the same part exactly when their intervals overlap. So the parts are the connected groups of overlapping intervals — which is Merge Intervals (4.27.2).
The sweep above is merging those intervals without ever building them, because walking the string visits them in order of their start already.
Saying this out loud is the strongest thing you can do on this problem. It shows you see the structure rather than the trick, and it is why this problem sits between the greedy and interval chapters.
Merge Intervals — the same merging, stated explicitly. 4.27.2.
Jump Game II — the same "extend the reach, then cut at the boundary" sweep. 4.26.3. These two problems have almost identical code but completely different stories.
Video Stitching, Minimum Taps — interval covering with the same reach-extension loop.
"Why must a part reach the last occurrence of every letter inside it?" Otherwise that letter appears in two parts.
"Why is cutting as early as possible optimal?" The boundary is forced, and cutting at the first legal point maximises the count.
"How do you get the last occurrences?" One pass, letting later writes overwrite earlier ones.
"What is the space complexity?"O(1) — 26 letters, fixed. Say why it is constant rather than O(n).
"Is this related to any other problem?" Merge Intervals, with one interval per letter.
One thing to volunteer: the interval framing, and the fact that this is Jump Game II's loop with a different meaning. Two connections in one sentence each, and both show the pattern rather than the puzzle.