Partition Labels
Medium · greedy
You are given a string s of lowercase English letters. Cut it into consecutive pieces, with no characters left over, so that no letter appears in more than one piece. A letter may appear many times, as long as all of its occurrences are in the same piece.
Cut it into as many pieces as possible, and return a list with the length of each piece, in the order the pieces appear in s. The lengths always add up to len(s).
Examples
Example 1
Input: s = "abacdcefe"
Output: [3, 3, 3]
The pieces are "aba", "cdc" and "efe". No letter is shared, and no piece can be cut any further.
Example 2
Input: s = "mississippi"
Output: [1, 10]
The "m" appears once, so it is a piece by itself. The "i" appears at both ends of the rest, which pulls everything between into one piece.
Example 3
Input: s = "qwerty"
Output: [1, 1, 1, 1, 1, 1]
Every letter is different, so every character can be its own piece.
Constraints
- 1 <= len(s) <= 2000
- s contains only lowercase English letters