#763
Partition Labels
Medium Last occurrence
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Split a string into as many parts as possible so each letter appears in at most one part. Return the part sizes.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: cut the string into as many parts as possible with no letter in two parts.
Why this works: a part must reach the last occurrence of every letter inside it; cut when the scan reaches that point.
Example: "ababcbacadefegdehijhklij"
first part ends at last 'a' (index 8) → 9then "defegde" → 7, then "hijhklij" → 8
✦Hints open one at a time
Record the last index of every letter.
While scanning, a part must extend at least to the last index of every letter in it.
↗Approach
Keep end = max last-index seen in the current part. When i reaches end, close the part and start a new one.
</>Solution (Java)
import java.util.*;
class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
List<Integer> res = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last[s.charAt(i) - 'a']);
if (i == end) { // everything in the part ends here
res.add(end - start + 1);
start = i + 1;
}
}
return res;
}
}!Common mistake
Closing a part at the last index of only its first letter.
Complexity
- Time: O(n).
- Space: O(26).
Topic: Greedy
🎬 Episodes 69–73: video coming soon