题目链接

Leetcode.1593 拆分字符串使唯一子字符串的数目最大 Rating ： 1740

题目描述

给你一个字符串 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<=161 <= s.length <= 161<=s.length<=16

• s仅包含小写英文字母

解法：哈希表 + 回溯

由于本题数据量非常小，我们可以通过 回溯 求出所有分割字符串的方案。

回溯过程中用一个 哈希表 uset记录已经被分割的子串。

如果 uset中已经存在当前被分割的子串 t，t就不符合要求，将 t包含下一个字符，再做同样的操作。

枚举子串的起始下标 u，如果 u >= s.size()，说明已经分割完一个方案了，uset.size()就是当前分割方案的答案。

我们用一个全局变量 ans记录最大值。

剪枝：

如果 n - u + uset.size() <= ans，就直接返回。这个式子的意义是，当前已经被分割好的唯一子串数量 uset.size()+ 剩下未被分割的最大可能子串数量 都小于等于 ans。说明就是递归到最后，ans也不会变得更大，所以这是无用的操作，可以直接返回。

时间复杂度： O(2n∗n)O(2^n * n)O(2n∗n)

C++代码：

class Solution {
public:int ans = 0,n;void dfs(int u,string &s,unordered_set &uset){if(n - u + uset.size() <= ans) return;if(u == n){int m = uset.size();ans = max(ans,m);return;}for(int i = u;i < n;i++){string t = s.substr(u,i - u + 1);if(uset.count(t)) continue;uset.insert(t);dfs(i + 1,s,uset);uset.erase(t);}}int maxUniqueSplit(string s) {unordered_set uset;n = s.size();dfs(0,s,uset);return ans;}
};