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 <= 105sconsists of only English lowercase letters.
Solutions
Solution 1: Greedy
According to the problem description, each substring should be as long as possible and contain unique characters. Therefore, we can greedily partition the string.
We define a binary integer mask to record the characters that have appeared in the current substring. The i-th bit of mask being 1 indicates that the i-th letter has already appeared, and 0 indicates that it has not appeared. Additionally, we need a variable ans to record the number of substrings, initially ans = 1.
Traverse each character in the string s. For each character c, convert it to an integer x between 0 and 25, then check if the x-th bit of mask is 1. If it is 1, it means the current character c is a duplicate in the current substring. In this case, increment ans by 1 and reset mask to 0. Otherwise, set the x-th bit of mask to 1. Then, update mask to the bitwise OR result of mask and 2x.
Finally, return ans.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
class Solution: def partitionString(self, s: str) -> int: ans, mask = 1, 0 for x in map(lambda c: ord(c) - ord("a"), s): if mask >> x & 1: ans += 1 mask = 0 mask |= 1 << x return ans(code-box)
