You are given a string s of lowercase letters. Cut it into consecutive pieces so that each letter appears in at most one piece: all the as end up in the same piece, all the bs in the same piece, and so on. Among all ways to do that, make as many pieces as possible.
Write piece_sizes(s: str) -> list[int] that returns the lengths of the pieces, from left to right. (The best cut is unique, so there is exactly one right answer.)
piece_sizes("abacdcdeffe") # [3, 4, 4] "aba" | "cdcd" | "effe"
piece_sizes("bookkeeper") # [1, 2, 2, 4, 1] "b" | "oo" | "kk" | "eepe" | "r"
piece_sizes("mississippi") # [1, 10] "m" | "ississippi"
piece_sizes("abc") # [1, 1, 1]
Constraints:
1 <= len(s) <= 5 * 10^5scontains only lowercase English letters
Aim for O(n) time. Searching the rest of the string again for each character is O(n²) and fails the large tests.
Show hint
once a piece contains a letter, it has to stretch at least as far as that letter's last appearance in s.