1593. 拆分字符串使唯一子字符串的数目最大

🎯 问题描述（来源于LeetCode）

描述：
给定一个字符串 s，请你将该字符串分割成若干非空子串，使得所有子串都是互不相同的。
返回可以分割得到的最大子串数目。

说明：

子串是原字符串中连续的一段。
分割方案中，所有子串按原顺序拼接应等于 s。
相同子串不能出现两次。

示例：

示例 1：

1
2
3

输入: s = "ababccc"
输出: 5
解释: 一种分割方式为 ["a", "b", "ab", "c", "cc"]，共 5 个互不相同的子串。

示例 2：

1
2
3

输入: s = "aba"
输出: 2
解释: 一种分割方式为 ["a", "ba"] 或 ["ab", "a"]，最多 2 个。

示例 3：

1
2
3

输入: s = "aa"
输出: 1
解释: 只能分割成 ["aa"]，因为 ["a","a"] 含有重复子串。

💻 解题思路

思路：回溯法（DFS）枚举所有分割

算法步骤

获取字符串长度 n，初始化全局变量 ans = 0（记录最大子串个数）和一个集合 seen（存储已出现的子串）。
定义递归函数 dfs(start)，表示当前要从下标 start 开始分割：
- 如果 start == n（已到达末尾），更新 ans = max(ans, len(seen)) 并返回。
- 否则，枚举子串的结束位置 end 从 start+1 到 n，取子串 sub = s[start:end]：
  - 如果 sub 不在 seen 中（即未出现过），则：
    - 将 sub 加入 seen。
    - 递归调用 dfs(end)。
    - 回溯：从 seen 中移除 sub。
从 dfs(0) 开始搜索。
返回 ans。

代码实现

from typing import List

class Solution:
    def maxUniqueSplit(self, s: str) -> int:
        n = len(s)
        self.ans = 0
        seen = set()
        
        def dfs(start):
            if start == n:
                self.ans = max(self.ans, len(seen))
                return
            for end in range(start + 1, n + 1):
                sub = s[start:end]
                if sub not in seen:
                    seen.add(sub)
                    dfs(end)
                    seen.remove(sub)
        
        dfs(0)
        return self.ans

📊 性能分析

时间复杂度：最坏情况下为 $O(2^{n})$ ，因为每个位置都可能成为分割点，但实际通过集合剪枝会减少分支。对于 $n \leq 16$ （原题数据范围），此解法可以通过。
空间复杂度： $O(n)$ ，递归深度为 $n$ ，集合最多存储 $n$ 个子串。

思考

该回溯解法枚举了所有可能的分割方案，并通过集合 seen 保证子串互不相同，在到达字符串末尾时记录当前方案中的子串个数并更新全局最大值。
优点：

逻辑直观，直接模拟题意。
剪枝条件 sub not in seen 避免了重复子串的无效分支。
使用全局变量 self.ans 记录最大值，避免了传递多个参数。

注意事项：

由于字符串长度通常较小（LeetCode 原题中 $s.length \leq 16$ ），指数级搜索是可行的。若长度更大，可考虑使用记忆化搜索或更优的剪枝策略（如提前计算剩余字符能产生的最大可能子串数，但通常无需）。
递归过程中，每次都会尝试所有可能的 end，即使当前已经 start 很小，也可能产生大量分支。可优化枚举顺序：优先取更短的子串（但实际顺序不影响正确性）。
本题与「分割回文串」类似，但判断条件从“回文”变为“子串不重复”。