题目描述
给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：s = "ababccc"
输出：5
解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，因为其中的 'a' 和 'b' 都出现了不止一次。
示例 2：
输入：s = "aba"
输出：2
解释：一种最大拆分方法为 ['a', 'ba'] 。
示例 3：
输入：s = "aa"
输出：1
解释：无法进一步拆分字符串。
提示：
-
1 <= s.length <= 16
-
s 仅包含小写英文字母
解法
方法一：回溯 + 剪枝
我们定义一个哈希表 $\textit{st}$，用于存储当前已经拆分出的子字符串。然后我们使用深度优先搜索的方式，尝试将字符串 $\textit{s}$ 拆分成若干个唯一的子字符串。
具体地，我们设计一个函数 $\text{dfs}(i)$，表示我们正在考虑将 $\textit{s}[i:]$ 进行拆分。
在函数 $\text{dfs}(i)$ 中，我们首先判断如果当前已经拆分出的子字符串的数量加上剩余的字符数小于等于当前的答案，那么我们就没有必要继续拆分，直接返回。如果 $i \geq n$，那么说明我们已经完成了对整个字符串的拆分，我们更新答案为当前的子字符串数量和答案的较大值。否则，我们枚举当前子字符串的结束位置 $j$（不包括 $j$），并判断 $\textit{s}[i..j)$ 是否已经被拆分出来。如果没有被拆分出来，我们将其加入到哈希表 $\textit{st}$ 中，并继续递归地考虑拆分剩余的部分。在递归调用结束后，我们需要将 $\textit{s}[i..j)$ 从哈希表 $\textit{st}$ 中移除。
最后，我们返回答案。
时间复杂度 $O(n^2 \times 2^n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $\textit{s}$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution:
def maxUniqueSplit(self, s: str) -> int:
def dfs(i: int):
nonlocal ans
if len(st) + len(s) - i <= ans:
return
if i >= len(s):
ans = max(ans, len(st))
return
for j in range(i + 1, len(s) + 1):
if s[i:j] not in st:
st.add(s[i:j])
dfs(j)
st.remove(s[i:j])
ans = 0
st = set()
dfs(0)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | class Solution {
private Set<String> st = new HashSet<>();
private int ans;
private String s;
public int maxUniqueSplit(String s) {
this.s = s;
dfs(0);
return ans;
}
private void dfs(int i) {
if (st.size() + s.length() - i <= ans) {
return;
}
if (i >= s.length()) {
ans = Math.max(ans, st.size());
return;
}
for (int j = i + 1; j <= s.length(); ++j) {
String t = s.substring(i, j);
if (st.add(t)) {
dfs(j);
st.remove(t);
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution {
public:
int maxUniqueSplit(string s) {
unordered_set<string> st;
int n = s.size();
int ans = 0;
auto dfs = [&](this auto&& dfs, int i) -> void {
if (st.size() + n - i <= ans) {
return;
}
if (i >= n) {
ans = max(ans, (int) st.size());
return;
}
for (int j = i + 1; j <= n; ++j) {
string t = s.substr(i, j - i);
if (!st.contains(t)) {
st.insert(t);
dfs(j);
st.erase(t);
}
}
};
dfs(0);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | func maxUniqueSplit(s string) (ans int) {
st := map[string]bool{}
n := len(s)
var dfs func(int)
dfs = func(i int) {
if len(st)+n-i <= ans {
return
}
if i >= n {
ans = max(ans, len(st))
return
}
for j := i + 1; j <= n; j++ {
if t := s[i:j]; !st[t] {
st[t] = true
dfs(j)
delete(st, t)
}
}
}
dfs(0)
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | function maxUniqueSplit(s: string): number {
const n = s.length;
const st = new Set<string>();
let ans = 0;
const dfs = (i: number): void => {
if (st.size + n - i <= ans) {
return;
}
if (i >= n) {
ans = Math.max(ans, st.size);
return;
}
for (let j = i + 1; j <= n; ++j) {
const t = s.slice(i, j);
if (!st.has(t)) {
st.add(t);
dfs(j);
st.delete(t);
}
}
};
dfs(0);
return ans;
}
|