题目描述
思路解析动画文字版
记牢这套:每个位置从短到长尝试切段,段重复就跳过、不重复就切下去递归,到末尾用段数更新答案;再用「已切段数加剩余字符数」当上界剪枝。下面每一帧都在套它。
先看画面怎么摆。最上面这排 a、b、a、b 是原串 "abab" 的四个字符,谁被前面切走的段吃掉了,就变灰。中间「当前路径 path」是已经切下来的各段,它们必须两两不同,所以这一行同时就是我们去重用的集合。右边「已收集的结果 res」只记下能刷新最多段数的完整切法。我们从位置 0 开始尝试各种切法,追不过当前最多段数的分支会被直接剪掉,最后留下段数最多的那条。
从位置 0 起手,先试最短的一刀,只切一个字符 a。path 现在是空的,a 没出现过,不重复,可以切。
把 a 收进 path,集合变成只有 a,指针推进到位置 1,字符 a 变灰表示已经被吃掉,接着去切后面的 bab。
位置 1 还是先试一个字符 b。当前 path 里只有 a,没有 b,不重复,切下来。
b 收进 path,集合是 a 和 b 两段,指针到位置 2,前两个字符都变灰,只剩 ab 没切。
位置 2 先试一个字符 a。可是 path 里已经有 a 了,题目要求各段互不相同,这一刀切出来是重复段,作废,给它打个叉跳过。
那就把这一段往右延一个字符,变成 ab。path 里没有 ab,不重复,这一刀可以切。
ab 收进 path,指针正好走到字符串末尾,四个字符全变灰,一种完整切法成型:a 加 b 加 ab,三段全不一样,记进结果区。当前最优答案从 0 抬到 3。
这条分支到底了,往回退。先撤掉 ab、再撤掉 b,集合退回只剩 a,指针回到位置 1。刚才在这里只试过「切一个字符 b」,现在换更长的切法接着试。
在位置 1 改切两个字符 ba。path 里只有 a,没有 ba,不重复,切下来。
ba 收进 path,集合是 a 和 ba 两段,指针到位置 3,只剩最后一个字符 b 没切。
进下一层前先估个上界。已经切了 2 段,后面就剩 1 个字符,哪怕它单独成段,这条路最多也就 3 段。3 段追不过当前最优的 3 段,再往下也不可能更好,直接剪掉这条路。
撤掉 ba,回到位置 1,试最长的一刀 bab,一口气切到末尾。path 里没有 bab,不重复,可以切。
bab 切下去,指针到了末尾,这条路是 a 加 bab 两段。进这一层前先估上界:已切 2 段加剩 0 个字符等于 2,不超过当前最优的 3 段,直接剪掉,不记进结果区。
以 a 打头的分支都处理完了,能更优的留下、追不过 3 段的都剪掉,把 path 一路退到空,指针回到最开头。第一刀只试过「切一个字符 a」,现在换更长的第一刀接着试。
第一刀这次切两个字符 ab。path 是空的,当然不重复,切下来,指针推进到位置 2。
又到估上界的时候。已经切了 1 段,后面还剩 2 个字符,最多再添 2 段,合起来顶多 3 段。还是追不过当前最优的 3,剪掉。
撤掉 ab,第一刀再加长成 aba。path 空着,不重复,切下来,指针到位置 3。
继续估上界。已切 1 段,后面只剩 1 个字符,最多再添 1 段,顶多 2 段,更追不过 3 了,剪掉。
撤掉 aba,第一刀直接把整串 abab 当成一段切到底,path 空着不重复,切下来,指针到末尾。
整串当成一段,指针到了末尾,这条路只有 1 段。估上界:已切 1 段加剩 0 个字符等于 1,追不过当前最优的 3 段,剪掉,不记进结果区。
搜索到此结束。结果区里稳稳留下的只有 a、b、ab 这一条 3 段切法;其余每条路要么撞上重复段、要么估上界追不过 3 段被剪掉。这就证明了再也切不出超过 3 段的方案,所以答案就是 3。把 "abab" 切成 a、b、ab 三段,正是唯一子串数目最多的方案,跟开头说的对上了。
边界:单字符只能 1 段;"aa" 切两段会重复所以仍是 1 段;"ab" 能切成 a、b 两段不重复,答案 2。
三个追问:n 最大 16、切法约 2^(n-1) 再加剪枝完全跑得动;上界剪枝去掉答案不变只会变慢;各段互不相同导致状态难压,所以用回溯而非 DP。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def maxUniqueSplit(self, s: str) -> int: def dfs(i: int): nonlocal ans if len(st) + len(s) - i <= ans: return if i >= len(s): ans = max(ans, len(st)) return for j in range(i + 1, len(s) + 1): if s[i:j] not in st: st.add(s[i:j]) dfs(j) st.remove(s[i:j]) ans = 0 st = set() dfs(0) return ans复杂度
- 时间：O(n · 2ⁿ)，长度为 n 的串,切口位置在每两个字符之间,共 n-1 个缝,每个缝可切可不切,所以切法总数约 2^(n-1) 种;每条切法生成并哈希各段又要 O(n)。合起来大致 O(n · 2^n)。集合判重和上界剪枝能在实战中砍掉大量分支,n 不超过 16 时跑得很快
- 空间：O(n)，按峰值算。集合里最多同时存 n 段,但这些段加起来就是已切走的那段前缀,总字符数不超过 n,所以集合占 O(n);递归深度也不超过 n 层,栈是 O(n)。两者都是 O(n),合起来 O(n)
易错点
面试追问把动画讲成自己的话
追问字符串长度可以到 16,纯回溯枚举会不会超时?
追问那句上界剪枝去掉会怎样?
追问能不能用动态规划代替回溯?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
构建字典序最大的可行序列
LeetCode 1718 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题