A sorting line tags every arriving item with a single lowercase letter that encodes its color, and items arrive one at a time in a fixed order. A scanner groups the arriving items into contiguous batches, but it jams and rejects a batch the instant a color tag repeats inside it. Given the full arrival sequence of color tags, find the fewest number of contiguous batches the sequence can be split into so that no batch ever contains the same color tag twice.
s consisting only of lowercase English letters — the color tag of each item, in arrival order.Print a single integer: the minimum number of contiguous batches needed so that no batch contains a repeated letter.
1 <= |s| <= 10^5s consists only of lowercase English letters (a-z)Example 1
Input
abacaba
Expected
4
Explanation
Walking left to right and tracking the letters seen in the current batch: 'a' (batch={a}), 'b' (batch={a,b}), then 'a' again would duplicate — close the first batch as "ab" and start a new one with 'a'. Next 'c' (batch={a,c}), then 'a' again duplicates — close the second batch as "ac" and start a new one with 'a'. Next 'b' (batch={a,b}), then 'a' again duplicates — close the third batch as "ab" and start a final batch with 'a'. The string ends there. Batches: "ab", "ac", "ab", "a" — 4 batches total.
Example 2
Input
eeeeee
Expected
6
Explanation
Every 'e' after the first would immediately duplicate the single letter already in the current batch, so each 'e' must start its own new batch: "e", "e", "e", "e", "e", "e" — 6 batches total for the 6 characters.
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 →