题目描述

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

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

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

$1 <= s.length <= 16$

$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

(DFS爆搜) $时间复杂度：C(0, n - 1) + C(1, n - 1) + … + C(n - 1, n - 1)$

枚举每一种切分可能性，并通过切分出来的字串不能重复进行早停、剪枝，最后输出最长的长度。

时间复杂度

拆分字符串，即在字符串的间隙中加入隔板将它们隔开，所以时间复杂度大约是：
$C(0, n - 1) + C(1, n - 1) + … + C(n - 1, n - 1)$

参考文献

C++ 代码

class Solution {
private:
    unordered_set<string> used;
    int cur_max = 0;

public:
    int maxUniqueSplit(string s) {
        if (s.empty())
            return 0;

        int n = s.size();
        dfs(s, 0);

        return cur_max;
    }

    void dfs(const string &s, int idx){
        if (idx >= s.size()){
            cur_max = max(cur_max, (int)used.size());
            return;
        }

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