05 August 2008
给你一个字符串 s ，拆分该字符串，并返回拆分后唯一子字符串的最大数目。
字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。
注意：子字符串 是字符串中的一个连续字符序列。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
输入：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
解释：无法进一步拆分字符串。
拆分给定的字符串，要求拆分后的每个子字符串唯一，求子字符串的最大数目，可以通过回溯算法实现。
对于长度为 nn 的字符串，有 n-1n−1 个拆分点。从左到右遍历字符串，对于每个拆分点，如果在此拆分之后，新得到的一个非空子字符串（即拆分点左侧的最后一个被拆分出的非空子字符串）与之前拆分出的非空子字符串都不相同，则当前的拆分点可以进行拆分，然后继续对剩下的部分（即拆分点右侧的部分）进行拆分。
判断拆分出的非空子字符串是否有重复时，可以使用哈希表。
当整个字符串拆分完毕时，计算拆分得到的非空子字符串的数目，并更新最大数目。
时间复杂度：O(2^n × n)，其中 n 是字符串的长度。 回溯过程会遍历所有可能的拆分方案，长度为 n 的字符串有 n-1 个拆分点，每个拆分点都可以选择拆分或者不拆分，因此共有 2^n−1种拆分方案。 对于每种拆分方案，都需要判断拆分出的非空子字符串是否有重复，时间复杂度是 O(n)。 因此总时间复杂度是O(2^n ×n)。
空间复杂度：O(n)，其中 n 是字符串的长度。空间复杂度取决于集合的大小以及回溯过程中的递归调用层数。集合中的元素个数不会超过 n，递归调用层数不会超过 n。
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
class Solution {
int maxSplit = 1;
public int maxUniqueSplit(String s) {
Set<String> set = new HashSet<String>();
backtrack(0, 0, s, set);
return maxSplit;
}
public void backtrack(int index, int split, String s, Set<String> set) {
int length = s.length();
if (index >= length) {
maxSplit = Math.max(maxSplit, split);
} else {
for (int i = index; i < length; i++) {
String substr = s.substring(index, i + 1);
if (set.add(substr)) {
backtrack(i + 1, split + 1, s, set);
set.remove(substr);
}
}
}
}
}