A parade streamer is printed with one continuous strip of lowercase letters s, one letter per centimetre, read in order from one end to the other. A decorator wants to cut the streamer into consecutive segments that together cover the entire streamer with no gaps and no overlaps -- that is, partition s into an ordered sequence of non-empty, contiguous pieces whose concatenation, in order, reproduces s exactly.
The decorator's rule: no two segments may begin with the same letter. Every segment's first letter must differ from the first letter of every other segment.
Determine the maximum number of segments the streamer can be cut into under this rule.
A single line containing the string s, consisting only of lowercase English letters.
A single integer: the maximum possible number of segments.
Example 1
Input
abab
Expected
2
Explanation
Cut into "a" and "bab". The segments begin with 'a' and 'b', two different letters, so this cut is valid and gives 2 segments. A third segment is impossible because the streamer contains only two distinct letters ('a' and 'b'), and every extra segment would need to begin with a letter no earlier segment used -- so 2 is the maximum.
Example 2
Input
abcd
Expected
4
Explanation
Cut into "a","b","c","d". Each of the four segments begins with a different letter ('a','b','c','d'), matching the four distinct letters that appear in the streamer, so 4 segments is achievable and is also the maximum possible.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →