Partition the String into Unique Substrings

Given a string ( S ), partition it into the minimum number of substrings such that each substring contains only unique characters. In other words, for a valid partition ( S = s_1 + s_2 + \cdots + s_k ), every substring ( s_i ) must consist of distinct characters. You should use a greedy approach: traverse the string and whenever a repeating character is detected in the current substring, start a new substring. For example, if ( S = "abac" ), the answer is 2 because one possible partition is ( "ab" ) and ( "ac" ), each having all unique characters. Your program should read the input from standard input and output the result to standard output.

inputFormat

The input consists of a single line containing the string ( S ) ((1 \leq |S| \leq 10^5)). The string contains only lowercase English letters.

outputFormat

Output a single integer representing the minimum number of substrings needed such that every substring has all unique characters.## sample

abac

2