Unique Character Partitioning

Given a string S, partition it into the minimum number of parts such that no part contains any duplicate characters. In other words, every character in each part must be unique. Formally, if the string is split into parts \(P_1, P_2, \dots, P_k\), then for each part \(P_i\), all characters in \(P_i\) are distinct. Your goal is to compute the minimum possible \(k\).

Example: For the string "abac", one valid partition is "ab" and "ac", so the answer is 2.

The input will be provided as a single string from standard input and the output should be written to standard output.

inputFormat

The input consists of a single line containing a non-empty string S.

Constraints:

• The string S consists of lowercase English letters.
• 1 \(\leq\) length of S \(\leq 10^5\)

outputFormat

Output a single integer representing the minimum number of parts the string can be split into such that each part contains unique characters.

world

1