152. Label Partitions
A librarian wants to cut a long strip of letter stickers, given as the string s, into consecutive pieces. After cutting, every letter must appear in at most one piece, so that no letter is split between two pieces. She wants as many pieces as possible.
Return a list with the length of every piece, from left to right. The pieces together are the whole strip. A letter that occurs far apart forces everything between its first and its last occurrence into the same piece. Find the last position of every letter first, then cut greedily as soon as the current piece cannot be extended by any letter inside it.
Example 1
- Input:
- s = "qwqerrtyt"
- Output:
- [3,1,2,3]
- Explanation:
The pieces are qwq, e, rr and tyt, so the lengths are 3, 1, 2 and 3.
Example 2
- Input:
- s = "aaaa"
- Output:
- [4]
- Explanation:
Only one letter is used, so the whole strip is one piece of length 4.
Constraints
1 ≤ s.length ≤ 105
s contains only lower case letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)