Learning Outcome
After this lesson, you should be able to use last occurrence positions as dynamic boundaries for greedy cuts.
Problem Statement
Given a string, partition it into as many parts as possible so each character appears in at most one part. Return the sizes of the parts.
| Input | Output | Why |
|---|---|---|
s = "ababcbacadefegdehijhklij" | [9,7,8] | The first partition must end at index 8 because a, b, and c all appear within that boundary. |
Brute Force Approach
Try every cut and validate whether characters appear across multiple parts. This is slow.
Optimized Approach
Precompute the last index of every character. While scanning, extend the current partition end to the farthest last occurrence seen so far.
Exact Pseudocode
last[ch] = final index of ch
start = 0
end = 0
for i from 0 to length(s) - 1:
end = max(end, last[s[i]])
if i == end:
answer.add(end - start + 1)
start = i + 1
return answerReference Code
class Solution:
def partitionLabels(self, s):
last = {ch: i for i, ch in enumerate(s)}
answer = []
start = 0
end = 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
answer.append(end - start + 1)
start = i + 1
return answerSample Dry Run
| Step | State | Result |
|---|---|---|
| Precompute last | a ends at 8, b at 5, c at 7 | Boundaries are known |
| Scan first partition | end expands to 8 | Cannot cut before 8 |
| i = 8 | i equals end | Add size 9 |
| Continue | Next partitions close at 15 and 23 | sizes [9,7,8] |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | The string is scanned twice. |
| Space | O(1) | For lowercase English letters, last positions use fixed space. |
Edge Cases
- A string with one repeated character becomes one partition.
- Each character must appear in at most one output part.
- Use the correct character range for the input.
Interview Checklist
- Precompute last occurrence for every character.
- Extend end while scanning the current partition.
- Cut only when i reaches end.
FAQs
Why can we cut when i equals end?
Every character seen in the current partition has its last occurrence at or before this index.
Why not cut at first repeat?
Other characters inside the segment may appear later, so the boundary must track all last occurrences.
What is the core pattern?
Last occurrence boundary greedy.