Minimum Unique Substrings Partition

Given a string s, partition it into the minimum number of contiguous substrings such that each substring contains only unique characters (i.e. no character appears more than once within any substring). This problem challenges you to determine the smallest integer k for which such a partition is possible.

Formally, if you partition s into k contiguous segments s = s1 s2 ... sk, every segment si must satisfy that all characters are distinct. Your task is to compute and output this minimum k.

The formula for the problem can be stated as follows:

Find the minimum k such that

\[ s = s_{1} s_{2} \quad\text{with} \quad \forall i, \; \text{all characters in } s_{i} \text{ are unique.} \]

inputFormat

The input is given via standard input (stdin) and consists of a single line containing the string s. The string is non-empty and may include any characters.

outputFormat

Output to standard output (stdout) a single integer: the minimum number of contiguous substrings required so that every substring has all unique characters.

## sample

abac

2