题目描述

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

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

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

样例

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

输入：s = "aba"
输出：2
解释：一种最大拆分方法为 ['a', 'ba'] 。

输入：s = "aa"
输出：1
解释：无法进一步拆分字符串。

提示：

• 1 <= s.length <= 16

• s 仅包含小写英文字母

算法分析

通过爆搜将s字符串的所有分割情况全部搜出来，并用set集合存储前面已经分割后的子符串，若枚举分割下一个子字符串时，必须保证set集合中不存在该子字符串，才能继续搜索下去，搜索完后，集合存的是所有不重复的拆分字符串，用集合的大小更新ans

时间复杂度

有剪枝处理，不好分析

Java 代码

class Solution {
    static HashSet<String> set = new HashSet<String>();
    static int ans = 0;
    static void dfs(String s, int u)
    {
        if(u == s.length())
        {
            ans = Math.max(ans, set.size());
            return ;
        }
        for(int i = u;i < s.length();i ++)
        {
            if(set.contains(s.substring(u, i + 1))) continue;
            set.add(s.substring(u, i + 1));
            dfs(s, i + 1);
            set.remove(s.substring(u, i + 1));
        }
    }
    public int maxUniqueSplit(String s) {
        ans = 0;
        dfs(s, 0);
        return ans;
    }
}