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 <= 105s 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
| class Solution:
def partitionString(self, s: str) -> int:
ss = set()
ans = 1
for c in s:
if c in ss:
ans += 1
ss = set()
ss.add(c)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int partitionString(String s) {
Set<Character> ss = new HashSet<>();
int ans = 1;
for (char c : s.toCharArray()) {
if (ss.contains(c)) {
++ans;
ss.clear();
}
ss.add(c);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int partitionString(string s) {
unordered_set<char> ss;
int ans = 1;
for (char c : s) {
if (ss.count(c)) {
++ans;
ss.clear();
}
ss.insert(c);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func partitionString(s string) int {
ss := map[rune]bool{}
ans := 1
for _, c := range s {
if ss[c] {
ans++
ss = map[rune]bool{}
}
ss[c] = true
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| function partitionString(s: string): number {
const set = new Set();
let res = 1;
for (const c of s) {
if (set.has(c)) {
res++;
set.clear();
}
set.add(c);
}
return res;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| use std::collections::HashSet;
impl Solution {
pub fn partition_string(s: String) -> i32 {
let mut set = HashSet::new();
let mut res = 1;
for c in s.as_bytes().iter() {
if set.contains(c) {
res += 1;
set.clear();
}
set.insert(c);
}
res
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def partitionString(self, s: str) -> int:
ans, v = 1, 0
for c in s:
i = ord(c) - ord('a')
if (v >> i) & 1:
v = 0
ans += 1
v |= 1 << i
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int partitionString(String s) {
int v = 0;
int ans = 1;
for (char c : s.toCharArray()) {
int i = c - 'a';
if (((v >> i) & 1) == 1) {
v = 0;
++ans;
}
v |= 1 << i;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int partitionString(string s) {
int ans = 1;
int v = 0;
for (char c : s) {
int i = c - 'a';
if ((v >> i) & 1) {
v = 0;
++ans;
}
v |= 1 << i;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func partitionString(s string) int {
ans, v := 1, 0
for _, c := range s {
i := int(c - 'a')
if v>>i&1 == 1 {
v = 0
ans++
}
v |= 1 << i
}
return ans
}
|
