难度: 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 仅包含小写英文字母
运行时间: 40 ms
内存: 16.2 MB
class Solution:
def maxUniqueSplit(self, s: str) -> int:
r = set()
n = len(s)
res = 0
def split(i):
if i == n:
nonlocal res
res = max(res, len(r))
for j in range(i + 1, n + 1):
if len(r) + 1 + n - j <= res:
break
if s[i:j] not in r:
r.add(s[i: j])
split(j)
r.remove(s[i: j])
split(0)
return res
本题解采用了回溯法来解决问题。首先，定义一个集合 `r` 来存储当前路径中的所有子字符串，保证它们的唯一性。`res` 变量用于记录最大的唯一子字符串数目。\n\n函数 `split(i)` 的参数 `i` 表示当前考虑的字符串的起始位置。如果 `i` 等于字符串的长度 `n`，说明已经检查完整个字符串，此时更新 `res` 的值。\n\n对于每个起始位置 `i`，循环尝试所有可能的结束位置 `j`。这里有一个剪枝操作：如果当前已有的唯一子字符串数加上剩余可能的最大子字符串数小于等于当前 `res`，则无需继续尝试，直接中断循环。如果从 `i` 到 `j` 的子字符串不在集合 `r` 中，则将其加入集合，递归地调用 `split(j)`，之后再将其从集合中移除，回溯到上一状态。
时间复杂度: O(2^n)
空间复杂度: O(n)
class Solution:
def maxUniqueSplit(self, s: str) -> int:
r = set() # 存储当前已生成的唯一子字符串集合
n = len(s) # 字符串的总长度
res = 0 # 最大唯一子字符串的数量
def split(i):
if i == n: # 如果已经处理完所有字符
nonlocal res
res = max(res, len(r)) # 更新最大唯一子字符串的数量
for j in range(i + 1, n + 1): # 尝试每一个可能的结束位置 j
if len(r) + 1 + n - j <= res: # 剪枝：如果当前组合的最大可能数量不会超过已知的最大数量，则停止尝试
break
if s[i:j] not in r: # 如果当前子字符串是唯一的
r.add(s[i: j]) # 添加到集合中
split(j) # 递归处理剩余字符串
r.remove(s[i: j]) # 回溯，移除当前子字符串，恢复状态
split(0)
return res # 返回最大唯一子字符串的数量
在回溯法中，剪枝操作是用来避免不必要的计算，从而提高算法效率的关键策略。具体到这个问题，剪枝操作基于当前已有的唯一子字符串数量和剩余字符串可能形成的最大唯一子字符串数量之和。如果这个总和小于或等于已经找到的最大数量（`res`），则表明即使加上所有可能的剩余子字符串，也无法超过当前的最大结果，因此，可以提前中断当前分支的探索。这样做可以显著减少不必要的递归调用，加速问题的解决。
回溯法适用于解决这类问题，因为它能够通过尝试所有可能的分割方式来寻找最大的唯一子字符串集合。与动态规划不同，回溯法在处理这种需要枚举所有可能情况的问题时更为直观和灵活。动态规划虽然可以用来解决某些优化问题，但在处理需要考虑多种分割可能性和维护一个全局最优解的问题时，可能不如回溯法有效，尤其是当问题的状态转移不易定义或者状态空间过大时。
在函数`split(i)`中，`j`代表当前考虑的子字符串的结束位置，由循环变量控制。从`i+1`到`n+1`的范围是合适的，因为它确保至少包含一个字符（即子字符串的最小长度为1）。此外，`n+1`作为上界使得`j`可以等于字符串的长度`n`，这样`s[i:j]`就能取到字符串s的最后一个字符。这是字符串分割问题中常用的一个技巧，以确保每次递归都能处理从当前位置到字符串结尾的所有可能的子字符串。
为了防止递归导致的栈溢出，可以考虑使用迭代的方式重写这个算法，或者使用显式栈来模拟递归过程。此外，可以采用尾递归优化，尽管Python默认不支持尾递归优化，但可以通过装饰器手动实现。另一种策略是增加递归调用的深度限制，配合更有效的剪枝策略减少递归的深度。最后，如果问题规模确实很大，可以考虑使用更加高效的数据结构或算法，例如动态规划或分治策略，以减少递归深度或总的运算量。