题目链接

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<=16$

• s仅包含小写英文字母

解法：哈希表 + 回溯

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

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

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

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

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

剪枝：

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

时间复杂度： $O(2^n\ast n)$

C++代码：

class Solution {
public:
    int ans = 0,n;

    void dfs(int u,string &s,unordered_set<string> &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<string> uset;
        n = s.size();
        dfs(0,s,uset);
        return ans;
    }
};