290. Partition into Substrings with Unique Characters

Given a string s, partition it into the minimum number of contiguous substrings such that no character repeats within any single substring. Return the number of substrings in this greedy partition.

Input: A quoted string s.

Output: Integer — number of substrings.

Examples

Input: "abac"
Output: 2
Explanation: 'aba' repeats 'a' so split: 'ab','ac'.

Input: "abc"
Output: 1
Explanation: All unique.

Input: "aaa"
Output: 3
Explanation: Each 'a' its own part.

Constraints

• 1<=s.length<=10^5

Asked by