Self-Contained Chunks
MediumIntervals
Problem
A string s of lowercase letters must be cut into consecutive pieces so that every letter appears in at most one piece. You want as many pieces as possible.
Return the lengths of the pieces, from left to right.
Example 1
- Input:
- s = "abacdcd"
- Output:
- [3, 4]
"aba" holds every a; "cdcd" holds every c and d.
Example 2
- Input:
- s = "qwqrr"
- Output:
- [3, 2]
Example 3
- Input:
- s = "xyz"
- Output:
- [1, 1, 1]
Constraints
- 1 ≤ s.length ≤ 10^5
- s contains only lowercase English letters.
Hint
Show the first hint
Each letter spans an interval from its first to its last occurrence. What does a valid cut have to respect?
Walkthrough
How to approach it
01Clarify before coding
- Is 'as many pieces as possible' unique? Yes, the maximal partition is unique, so the lengths are well defined.
- Only lowercase letters? Yes, 26 possible characters.
- Return lengths or the pieces? Lengths.
02Brute force
Try every set of cut positions and keep the valid one with the most pieces.
Cost: O(2^n · n): impossible beyond tiny strings.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.