Minimum Unique Substrings Partition

You are given a string s. Your task is to partition s into the minimum number of substrings such that each substring contains only unique characters (i.e. no duplicate characters appear within a substring).

More formally, let the required number be k, and let the substrings be s₁, s₂, ..., s_k. Then for each substring s_i, if we denote by S_i the set of characters in s_i, it must hold that:

[ |s_i| = |S_i| ]

Your solution should read the input from standard input and output the answer to standard output.

inputFormat

The input consists of a single line containing the string s. The string may be empty.

outputFormat

Output a single integer which is the minimum number of substrings into which the string can be partitioned such that each substring has all unique characters.

abac

2