Optimal Partition of String
Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.
Return the minimum number of substrings in such a partition.
Note that each character should belong to exactly one substring in a partition.
Example 1
Input
s = "abacaba"Output
4Two possible partitions are ("a", "ba", "cab", "a") and ("ab", "a", "ca", "ba"), and 4 is the minimum number of substrings needed.
Example 2
Input
s = "ssssss"Output
6The only valid partition is ("s", "s", "s", "s", "s", "s").
Constraints
- 1 <= s.length <= 10^5
- s consists of only English lowercase letters.
Asked at 4 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.