2405. Optimal Partition of String
Description
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: 4 Explanation: Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba"). It can be shown that 4 is the minimum number of substrings needed.
Example 2:
Input: s = "ssssss" Output: 6 Explanation: The only valid partition is ("s","s","s","s","s","s").
Constraints:
1 <= s.length <= 105
s
consists of only English lowercase letters.
Solutions
Solution 1: Greedy
According to the problem, each substring should be as long as possible and contain unique characters. We just need to partition greedily.
During the process, we can use a hash table to record all characters in the current substring, with a space complexity of $O(n)$; or we can use a number to record characters using bitwise operations, with a space complexity of $O(1)$.
The time complexity is $O(n)$, where $n$ is the length of the string $s$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Solution 2
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|