Minimum Partitions of Unique Substrings

You are given a string s consisting only of lowercase English letters. Your task is to partition s into the minimum number of substrings such that each substring contains only unique characters. In other words, within every partition no character appears more than once.

Formally, if you partition the string into substrings s₁, s₂, ..., s_k, then for each substring s_i every character must be unique. You need to determine the smallest possible k (number of partitions) such that the condition holds.

This can be mathematically represented by the following formula:

$$\min\;k \quad \text{such that} \quad \forall i,\; \forall c \in s_i,\; count(c) = 1.$$

If the input string is empty, output 0.

inputFormat

The input consists of a single line containing the string s (1 ≤ |s| ≤ 10⁵). The string consists only of lowercase English letters. An empty string is also possible.

outputFormat

Output a single integer, representing the minimum number of substrings needed so that each substring has all unique characters.

abac

2