Minimum Unique Substrings

Given a string S, partition it into the minimum number of substrings such that every substring contains only unique characters (i.e., no character appears more than once within the substring).

You can only break the string at a boundary between two characters. The task is to compute the minimal number of partitions required so that each resulting substring has all distinct characters. It is guaranteed that the input string is non-empty and consists only of lowercase letters.

The problem can be approached greedily: traverse the string character by character, and whenever a character repeats within the current substring, start a new substring.

This problem is rated easy.

inputFormat

The input consists of a single line containing the string S.

Constraints: 1 \(\leq\) |S| \(\leq\) 10⁵.

outputFormat

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

abac

2