The problem
Split a string into as many pieces as possible so that each letter appears in only one piece. Return the sizes of the pieces.
Input: "ababcbacadefegdehijhklij" Output: [9, 7, 8]
Picture it
Picture a ribbon of letters. First note where each letter appears for the last time. Walk along the ribbon, stretching the end of the current piece to the last appearance of every letter you pass. When your position reaches that end, every letter in the piece is finished, so you can cut there.
How to recognise it
- You cut a string into pieces so that a letter never appears in two pieces, and you want as many pieces as possible.
- Whichever piece holds the first copy of a letter must stretch to its last copy. That is a deadline, and deadlines can extend when you meet new letters inside the piece.
- The input is lowercase letters, up to 500 characters, so the exact limits are gentle, but a single pass with a lookup table is the intended shape.
- "Extend the current block to cover everything it forces, then cut" is the greedy interval-merging pattern.
Start with brute force
A cut between positions i − 1 and i is allowed exactly when the letters before the cut and the letters after it are disjoint. Test every cut position and use all the allowed ones.
def partition_brute(s):
n = len(s)
cuts = [0] + [i for i in range(1, n) if not (set(s[:i]) & set(s[i:]))] + [n]
return [b - a for a, b in zip(cuts, cuts[1:])]
For each of the n − 1 cuts the two sets cost O(n) to build, so time is O(n²). That is fine for 500 characters (about 250,000 steps) but it does not scale, and the idea below is simpler to run. Space is O(n) for the sets.
From brute force to the idea
- Record deadlines.
last[ch]is the index of the final copy of each letter. A piece containingchmust reach at least that index. - Grow the current piece. Walk the string. For each position keep
end = max(end, last[ch]): the farthest index the piece is forced to reach so far. - Cut when the deadline is met. When
i == end, every letter seen in this piece has its last copy at or before i, so nothing later belongs to this piece. Record the sizeend - start + 1. - Start the next piece at
i + 1.
Cutting as early as possible makes the pieces as small as possible, which gives the maximum number of pieces. Each cut is safe because no letter on the left appears on the right.
This is the key idea: extend the current piece to the last occurrence of every letter inside it, and cut the moment you reach that end.
The key idea
end = max(end, last[c]); cut when i == end. O(n).
Python solution
def partition_labels(s):
last = {ch: i for i, ch in enumerate(s)}
sizes, start, end = [], 0, 0
for i, ch in enumerate(s):
end = max(end, last[ch]) # this piece must reach ch’s last copy
if i == end:
sizes.append(end - start + 1) # safe to cut here
start = i + 1
return sizesIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): n − 1 cuts, each with two sets built in O(n) | O(n): the sets |
| Last-index scan (shown code) | O(n): one pass to build last, one pass to cut | O(1): at most 26 letters in last (plus the list of sizes) |
Edge cases
- One letter (
"a"): returns[1]. - All the same (
"aaaa"): returns[4]; one letter forces one piece. - All different (
"abc"): returns[1, 1, 1]. - Interleaved (
"abab"): returns[4]; the lastbforces the end. - Standard example
"ababcbacadefegdehijhklij": returns[9, 7, 8]. - A letter that spans nearly everything (
"eccbbbbdec"): returns[10], because the firstehas its last copy at the very end. - Empty string: returns
[]; the problem guarantees at least one letter.
Common mistakes
- Forgetting
start = i + 1, so later sizes are measured from the beginning:"abc"gives[1, 2, 3]. - Using
end = last[ch]instead of the maximum, which can shrink the deadline:"abab"returns[3, 1], and a letter appears in two pieces. - Building
lastfrom first occurrences instead of last ones. - Cutting when a letter's first copy ends, rather than when the whole piece's deadline is reached.
Return the pieces themselves as strings instead of their sizes. For "ababcbacadefegdehijhklij" the answer is ["ababcbaca", "defegde", "hijhklij"]. Describe your approach, then write it if you like.
Compare with our answer
The same scan, but slice the string when you cut.
def partition_pieces(s):
last = {ch: i for i, ch in enumerate(s)}
pieces, start, end = [], 0, 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
pieces.append(s[start:end + 1])
start = i + 1
return pieces
partition_pieces("abab") is ["abab"] and partition_pieces("abc") is ["a", "b", "c"]. Time O(n), space O(n) for the output.
A strong answer mentions: the last dictionary, end as the maximum deadline, cutting at i == end, slicing s[start:end + 1], and moving start forward.
1. You must split a log string into as many chunks as possible so that no event code appears in two chunks. Which approach fits best?
A chunk must reach the last copy of every letter in it, so the cut comes when the position equals the largest last index seen. Cutting at repeats, at changes or on sorted letters can leave a letter in two chunks.
2. What does end represent in the shown code?
end is the maximum of last[ch] over the letters in the current piece. It grows when a new letter's last copy lies further out and the cut happens when i catches up with it. It is not a size and not tied to the whole string.
3. A learner deletes the line start = i + 1. For which input is the output now wrong?
Without moving start, every size after the first is measured from index 0, so "abc" gives [1, 2, 3] instead of [1, 1, 1]. The other inputs produce a single piece, so the stale start is never used.
Score 60% or more and the lesson is marked complete.