631. Splitting So No Letter Is Shared
Split a string into consecutive pieces so that each LETTER appears in at most one piece. Make the number of pieces as LARGE as possible.
Print the sizes of the pieces, in order, separated by single spaces.
ababcbacadefegdehijhklij -> 9 7 8
abc -> 1 1 1
abcabc -> 6 every letter appears in both halves
## Where a piece is forced to end
If a letter appears at position p, then the piece containing p must also contain every
other occurrence of that letter, so it must reach at least as far as that letter's LAST
occurrence.
So precompute, for each letter, the last position it appears. Then sweep with two indices: the current piece's start, and the furthest position the piece is so far obliged to reach.
last[c] = the final index of letter c
start = 0, end = 0
for i in 0 .. n-1:
end = max(end, last[s[i]])
if i == end:
emit i - start + 1
start = i + 1
## Why cutting at the first legal point is right
The greedy closes a piece the moment it is allowed to, and that gives the MOST pieces.
Suppose some optimal split has a piece running from start to q, where q > end and end
was the first legal cut. Everything in start .. end has all its occurrences inside that
range, by the definition of end. So cutting at end is legal, and the remainder
end+1 .. q is then a piece on its own or the start of one. Either way the split has at least
as many pieces.
Cutting later can only merge pieces together, never separate them, so cutting as early as legally possible is never worse.
## Why end can only grow
end is a running maximum and never moves backwards. That is what makes the sweep linear:
i walks forward once, end walks forward once, and the test i == end fires exactly when a
piece closes.
If end could shrink, the test would fire in the wrong place; it cannot, because max only
ever raises it.
## The inputs worth tracing
abcabc answers 6: every letter appears in both halves, so nothing can be cut and the whole
string is one piece.
abab answers 4 for the same reason at a smaller size, and abc answers 1 1 1 because no
letter repeats at all. Those three bracket the behaviour.
## Cost
Time O(n) after one pass to build the last-occurrence table. Space O(1), since the table has
one entry per letter of the alphabet.
Constraints - `1 ≤ length ≤ 200000` - the string contains only lowercase letters
Input
One line containing a non-empty string of lowercase letters.
Output
Print the sizes of the pieces in order, on one line, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.