The problem
Cut a string s into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts, in order.
Examples
01
- Input
s = "ababcbacadefegdehijhklij"
- Output
[9, 7, 8]
02
- Input
s = "eccbbbbdec"
- Output
[10]
Constraints
- 1 ≤ s.length ≤ 500
- Only lowercase English letters.
The idea
A part that contains a letter must stretch at least to that letter’s last appearance. So first record where each letter appears for the last time.
Walk the string, stretching the current part’s end to the last appearance of every letter met. When the walk reaches end, every letter inside has finished — cut there, as early as possible, which makes the parts as many as possible.
- Time
- O(n)
- Space
- O(1) — 26 positions
Solution · every language run against every case
class Solution: def partitionLabels(self, s: str) -> List[int]: last = {c: i for i, c in enumerate(s)} # where each letter appears for the last time sizes = [] start = end = 0 for i, c in enumerate(s): end = max(end, last[c]) # this part must reach at least that far if i == end: # every letter seen so far is finished: cut here sizes.append(end - start + 1) start = i + 1 return sizes