Minimum Unique Substring Cover

You are given a string S.

You need to split it into the minimum number of contiguous substrings such that:

Conditions:

• Each substring must contain no repeating characters

• Every character of the original string must be used

• Substrings must remain contiguous

• Your task is to return the minimum number of substrings required.

📥 Input Format

• A single string S

📤 Output Format

• A single integer representing the minimum number of valid substrings

⚙️ Constraints

• 1≤∣S∣≤1051 \le |S| \le 10^51≤∣S∣≤105

🧪 Examples

Example 1

Input:

abac

Output:

2

Explanation: One valid split is: ab | ac

• "ab" → all unique

• "ac" → all unique

So minimum substrings = 2