Unique Substring Partition

Given a string \(S\), partition it into the minimum number of non-overlapping substrings such that each substring contains only unique characters. In other words, for every substring in the partition, no character appears more than once.

For example, if \(S = abac\), the optimal partition is ab|ac, yielding 2 substrings.

You are required to output the number of substrings in such an optimal partition.

inputFormat

The input consists of a single line containing the string \(S\). The string may be empty and will consist only of lowercase English letters.

outputFormat

Output a single integer denoting the minimum number of substrings that \(S\) can be partitioned into, such that each substring has all unique characters.

abac

2