Minimum Splits for Unique Character Strings

In this problem, you are given a string (s) and your task is to split it into as few substrings as possible such that each substring contains only unique characters. In other words, every character in each substring must appear exactly once.

For example:

• If \(s = \"abac\"\), one optimal split would be \(\"ab\", \"ac\"\) which gives a total of 2 substrings.
• If \(s = \"aaaa\"\), each character must be in its own substring, so the answer is 4.
• If \(s = \"abacabc\"\), one optimal way to split is \(\"ab\", \"ac\", \"abc\"\) resulting in 3 substrings.

The mathematical formulation of the problem is as follows:

$$\text{minimize } k, \quad \text{subject to: each substring } s_i \subset s \text{ has all unique characters.} $$

Your solution should read the input string from standard input and output the minimum number of substrings required to meet the condition.

inputFormat

The input consists of a single line containing the string (s). The string may be empty and can contain any characters.

outputFormat

Output a single integer representing the minimum number of substrings the string can be split into such that each substring contains unique characters.## sample

abac

2