1058. Fewest Pieces With No Letter Twice
A lowercase string is given. Cut it into consecutive pieces so that NO PIECE contains the same letter twice. Print the FEWEST pieces needed.
abacaba -> 4 ab | ac | ab | a
abcabcabc -> 3 abc | abc | abc
ssssss -> 6 every letter is its own piece
abcdefghij -> 1
## What most people try first
A table: best[i] is the fewest pieces covering the first i characters, filled by trying
every earlier cut. That is O(n^2) splits and it is the brute force this problem was checked
against. At n = 200000 it is 4 * 10^10.
## Extend the current piece until it would break
seen = empty set
pieces = 1
for each character c:
if c is in seen:
pieces += 1
seen = { c } start a fresh piece holding just c
else:
add c to seen
The set never holds more than 26 letters, so it can be 26 booleans rather than a hash set.
## Why cutting as late as possible is right
The claim is: after p pieces, the greedy has covered at least as many characters as any
legal cutting's first p pieces. Write G(p) for how far the greedy has got and O(p)
for how far the other cutting has got, both measured as the number of characters consumed.
Induction on p. At p = 0 both are 0.
Suppose G(p) >= O(p). The other cutting's next piece is s[O(p) .. O(p+1) - 1], and it
is repeat-free because that cutting is legal.
If G(p) >= O(p+1), then G(p+1) > G(p) >= O(p+1) already, since a piece is never empty.
Otherwise G(p) < O(p+1). Look at s[G(p) .. O(p+1) - 1]. Because O(p) <= G(p), that
is a SUBSTRING of the other cutting's next piece, and a substring of a repeat-free string is
repeat-free. So a piece starting at G(p) is legal at least as far as O(p+1) - 1, and
the greedy takes the longest legal piece from its start, giving G(p+1) >= O(p+1).
Either way G(p+1) >= O(p+1), which closes the induction.
So for the cutting that uses the fewest pieces, say m of them, the greedy has covered the
whole string after m pieces too, and therefore uses at most m. Since m is the
minimum, it uses exactly m.
The single step doing the work is "a substring of a repeat-free string is repeat-free". That is the property of the piece condition that makes the late cut safe, and a condition without it, such as "the piece must contain at least three distinct letters", breaks the argument immediately.
## Where this sits
Problem #631 cuts the SAME kind of string with the opposite rule: there a letter may not appear
in two different pieces, and the objective is the LARGEST number of pieces. The two look alike
and share nothing. On abcabc, #631 answers 1, because a appears in both halves so the
whole string must stay together; this problem answers 2, because each abc is internally
repeat-free.
Having both in the bank is deliberate. If you can say which is which from the statement alone, you have understood the pattern rather than the wording.
## The reset
When a repeat forces a cut, the new piece must contain the CURRENT character. Resetting the set
to empty and moving on loses that character and answers ssssss as 3 instead of 6.
## Overflow
The answer is at most n = 200000. Nothing here is near the 32 bit limit of 2147483647.
## Cost
Time O(n). Space O(1), since the alphabet is fixed at 26.
Constraints - `1 ≤ length ≤ 200000` - the line contains lowercase letters only
Input
A single line containing the lowercase string.
Output
Print one integer alone on a line: the fewest consecutive pieces such that no piece contains a repeated letter. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.