Description
Given a string s, partition it into one or more substrings such that each character appears in at most one substring. Return minimum number of substrings.
Examples
Input:
s = "abacaba"Output:
4Explanation:
Greedy partition: 'ab', then 'a' repeats so new partition, 'cab', then 'a' repeats. Total: 4 substrings.
Input:
s = "abcdef"Output:
1Explanation:
The entire string "abcdef" contains all unique characters, so no partitioning is needed. It is possible to keep it as one substring.
Input:
s = "aabbcc"Output:
4Explanation:
Partition at each duplicate: "aa", "bb", "cc". Each partition contains only one unique character repeated, which satisfies the constraint that each substring has unique characters within itself.
Constraints
- •
1 ≤ s.length ≤ 10⁵