题目描述

给你一个字符串 s ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。

字符串 s 拆分后可以得到若干 非空子字符串 ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 唯一的 。

注意：子字符串 是字符串中的一个连续字符序列。

样例

输入：s = "ababccc"
输出：5
解释：一种最大拆分方法为 ['a', 'b', 'ab', 'c', 'cc'] 。像 ['a', 'b', 'a', 'b', 'c', 'cc'] 这样拆分不满足题目要求，因为其中的 'a' 和 'b' 都出现了不止一次。

提示：

• 1 <= s.length <= 16

• s 仅包含小写英文字母

算法

(回溯) $O(2^n)$

直接暴力回溯，使用哈希表存储已经遍历的子字符串，当哈希表中存在子字符串，则跳过，否则存储子字符串，进入下一个回溯情况。最后根据idx的位置判断是否遍历完字符串，然后哈希表的大小即为子字符串个数，取最大个数即可。

时间复杂度

设字符串长度为n，则共有n-1个间隙，我们可以选择每个间隙分割或不分割，所以共$O(2^n)$的复杂度

C++ 代码

class Solution {
public:
    int ans;
    void dfs(string &s, unordered_set<string> &hash, int idx){
        if(idx==s.size()){
            ans=max(ans, (int)hash.size());
            return;
        }

        for(int len=1;idx+len-1<s.size();len++){
            string t=s.substr(idx, len);
            if(hash.count(t)) continue;
            hash.insert(t);
            dfs(s, hash, idx+len);
            hash.erase(t);
        }

    }
    int maxUniqueSplit(string s) {
        unordered_set<string> hash;
        ans=0;
        dfs(s, hash, 0);
        return ans;
    }
};