Medium

题目描述

给定一个字符串 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 只包含小写英文字母。

解题思路

这是一道经典的回溯搜索问题。我们需要尝试所有可能的拆分方式，找出能产生最多唯一子字符串的方案。

核心思路

  1. 回溯搜索：从字符串的第一个位置开始，尝试不同长度的子字符串
  2. 唯一性检查：使用哈希集合记录已经使用过的子字符串，确保每个子字符串都是唯一的
  3. 剪枝优化：当当前拆分数量加上剩余字符串的最大可能拆分数量都不如已知最优解时，提前返回

具体步骤

  • 定义递归函数 backtrack(index)，表示从位置 index 开始拆分剩余字符串
  • 在每个位置，尝试所有可能的子字符串长度（从1到剩余长度）
  • 如果当前子字符串未被使用过，将其加入已使用集合，递归处理剩余部分
  • 回溯时移除当前子字符串，尝试下一种可能
  • 维护全局最优解

由于字符串长度最大为16，暴力搜索的时间复杂度是可以接受的。关键的优化在于剪枝：如果当前方案即使将剩余字符串每个字符都单独拆分也无法超越已知最优解，就提前终止搜索。

代码实现

class Solution {
public:
    int maxUniqueSplit(string s) {
        unordered_set<string> used;
        int maxSplit = 0;
        backtrack(s, 0, used, maxSplit);
        return maxSplit;
    }
    
private:
    void backtrack(const string& s, int start, unordered_set<string>& used, int& maxSplit) {
        // 剪枝：即使剩余字符都单独拆分也无法超越当前最优解
        if (used.size() + (s.length() - start) <= maxSplit) {
            return;
        }
        
        if (start == s.length()) {
            maxSplit = max(maxSplit, (int)used.size());
            return;
        }
        
        for (int end = start + 1; end <= s.length(); end++) {
            string substr = s.substr(start, end - start);
            if (used.find(substr) == used.end()) {
                used.insert(substr);
                backtrack(s, end, used, maxSplit);
                used.erase(substr);
            }
        }
    }
};

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        def backtrack(start, used):
            # 剪枝：即使剩余字符都单独拆分也无法超越当前最优解
            if len(used) + (len(s) - start) <= self.max_split:
                return
            
            if start == len(s):
                self.max_split = max(self.max_split, len(used))
                return
            
            for end in range(start + 1, len(s) + 1):
                substr = s[start:end]
                if substr not in used:
                    used.add(substr)
                    backtrack(end, used)
                    used.remove(substr)
        
        self.max_split = 0
        backtrack(0, set())
        return self.max_split

public class Solution {
    private int maxSplit = 0;
    
    public int MaxUniqueSplit(string s) {
        HashSet<string> used = new HashSet<string>();
        Backtrack(s, 0, used);
        return maxSplit;
    }
    
    private void Backtrack(string s, int start, HashSet<string> used) {
        // 剪枝：即使剩余字符都单独拆分也无法超越当前最优解
        if (used.Count + (s.Length - start) <= maxSplit) {
            return;
        }
        
        if (start == s.Length) {
            maxSplit = Math.Max(maxSplit, used.Count);
            return;
        }
        
        for (int end = start + 1; end <= s.Length; end++) {
            string substr = s.Substring(start, end - start);
            if (!used.Contains(substr)) {
                used.Add(substr);
                Backtrack(s, end, used);
                used.Remove(substr);
            }
        }
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var maxUniqueSplit = function(s) {
    const backtrack = (index, used) => {
        if (index === s.length) {
            return 0;
        }
        
        let maxCount = 0;
        for (let i = index + 1; i <= s.length; i++) {
            const substring = s.slice(index, i);
            if (!used.has(substring)) {
                used.add(substring);
                maxCount = Math.max(maxCount, 1 + backtrack(i, used));
                used.delete(substring);
            }
        }
        
        return maxCount;
    };
    
    return backtrack(0, new Set());
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(2^n × n)，其中 n 是字符串长度。最坏情况下需要尝试所有可能的拆分方案，每种方案需要 O(n) 时间处理字符串操作
空间复杂度O(n)，递归栈深度最大为 n，哈希集合最多存储 n 个子字符串