1593. 拆分字符串使唯一子字符串的数目最大
1593. 拆分字符串使唯一子字符串的数目最大
题目
Given a string s
, return the maximum number of unique substrings that the given string can be split into.
You can split string s
into any list of non-empty substrings , where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "ababccc"
Output: 5
Explanation : One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.
Example 2:
Input: s = "aba"
Output: 2
Explanation : One way to split maximally is ['a', 'ba'].
Example 3:
Input: s = "aa"
Output: 1
Explanation : It is impossible to split the string any further.
Constraints:
1 <= s.length <= 16
s
contains only lower case English letters.
题目大意
给你一个字符串 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
仅包含小写英文字母
解题思路
这道题可以使用回溯算法来生成所有可能的子字符串组合。
使用一个集合(或对象)来跟踪当前子字符串组合中的唯一子字符串;
回溯法生成子字符串:
- 从字符串的起始位置开始,尝试每一个可能的结束位置,生成子字符串;
- 对于每个生成的子字符串,检查它是否已经存在于集合中:
- 如果不存在,则将其添加到集合中并继续递归;
- 如果存在,则回溯,尝试其他组合;
回溯结束条件:
- 在每次递归调用中,判断是否已经遍历到了字符串末尾;
- 记录当前的唯一子字符串数量,并与最大数量进行比较,更新最大数量;
复杂度分析
- 时间复杂度:
O(n * 2^n)
,其中n
是字符串的长度,生成所有子字符串组合的可能性呈指数增长。 - 空间复杂度:
O(n)
,用于存储当前的子字符串和唯一子字符串集合。
代码
/**
* @param {string} s
* @return {number}
*/
var maxUniqueSplit = function (s) {
let maxCount = 0;
const backtrack = (start, set) => {
if (start == s.length) {
maxCount = Math.max(maxCount, set.size);
return;
}
for (let end = start + 1; end <= s.length; end++) {
const substring = s.slice(start, end);
if (!set.has(substring)) {
set.add(substring); // 添加到集合
backtrack(end, set); // 递归
set.delete(substring); // 回溯
}
}
};
backtrack(0, new Set());
return maxCount;
};