mediumGreedy choiceHash maps and sets target 25 min
Cut a string by its letters
You get a string s of lowercase letters. Cut it into pieces, left to right, so that every letter appears in only one piece: all the copies of a letter must end up in the same piece. Make as many pieces as possible.
Return the lengths of the pieces, in order from left to right.
Example 1
Input
s = "abacdcd"Output[3, 4]The pieces are aba and cdcd. The first piece must hold both a's, at positions 0 and 2, and the b sits between them.
Example 2
Input
s = "babcdee"Output[3, 1, 1, 2]The pieces are bab, c, d and ee.
Example 3
Input
s = "rotor"Output[5]The r at both ends forces one piece: the whole string.
Constraints
1 ≤ len(s) ≤ 105
sholds only the lowercase letters a to z.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.