Partition Labels
The key idea
A letter forces every part that contains it to also contain its last occurrence. So scan left to right and keep extending the current part's right edge to the farthest last-occurrence of any letter seen so far. When the scan index reaches that edge, no earlier letter can reach past it — cut the part there.
Problem
You are given a string s. We want to partition s into as many parts as possible so that each letter appears in at most one part. Note that the partition is done so that, after concatenating all the parts in order, the resultant string is s.
Return a list of integers representing the size of these parts.
Constraints
1 <= s.length <= 500sconsists of lowercase English letters.
Examples
Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Input: s = "eccbbbbdec"
Output: [10]
Input: s = "abac"
Output: [3,1]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Greedy problems
- Assign CookiesEASY
- Best Time to Buy and Sell Stock IIMEDIUM
- Boats to Save PeopleMEDIUM
- Can Place FlowersEASY
- CandyHARD
- Dota2 SenateMEDIUM
- Gas StationMEDIUM
- Hand of StraightsMEDIUM
- Increasing Triplet SubsequenceMEDIUM
- Jump GameMEDIUM
- Jump Game IIMEDIUM
- Lemonade ChangeEASY