题目描述
思路解析动画文字版
核心三句话：串变指纹、按位与为 0 才能拼、DFS 选与不选并随时刷新最大长度。下面每帧都在套它。
预处理 · 准备建指纹：先扫一遍数组，把每个串变成它用到的字母集合（指纹）。指纹相当于这个串占用了哪些字母。
指纹 · "un"："un" 内部没有重复字母，合法。它占用的字母集是 {u、n}，记下这枚指纹。
指纹 · "iq"："iq" 内部没有重复字母，合法。它占用的字母集是 {i、q}，记下这枚指纹。
指纹 · "ue"："ue" 内部没有重复字母，合法。它占用的字母集是 {u、e}，记下这枚指纹。
起点 · 空串：从空串出发，还没选任何串，长度 0。接下来逐个候选串试着往里选。
查看 · "un"：试候选 "un"（占用 {u、n}）。它和当前已选 空串 没有公共字母，按位与为 0，可以选入。
合法 · "un"：当前已串联 "un"，长度 2，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 2。
查看 · "iq"：试候选 "iq"（占用 {i、q}）。它和当前已选 "un" 没有公共字母，按位与为 0，可以选入。
合法 · "uniq"：当前已串联 "uniq"，长度 4，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
冲突 · "ue"：试候选 "ue"，但它和当前已选 "uniq" 共用字母 {u}，按位与不为 0，会重复，排除掉、不选它。
回溯 · 撤销 "iq"：选入 "iq" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 "un"，再去试下一个候选。
冲突 · "ue"：试候选 "ue"，但它和当前已选 "un" 共用字母 {u}，按位与不为 0，会重复，排除掉、不选它。
回溯 · 撤销 "un"：选入 "un" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 空串，再去试下一个候选。
查看 · "iq"：试候选 "iq"（占用 {i、q}）。它和当前已选 空串 没有公共字母，按位与为 0，可以选入。
合法 · "iq"：当前已串联 "iq"，长度 2，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
查看 · "ue"：试候选 "ue"（占用 {u、e}）。它和当前已选 "iq" 没有公共字母，按位与为 0，可以选入。
合法 · "ique"：当前已串联 "ique"，长度 4，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
回溯 · 撤销 "ue"：选入 "ue" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 "iq"，再去试下一个候选。
回溯 · 撤销 "iq"：选入 "iq" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 空串，再去试下一个候选。
查看 · "ue"：试候选 "ue"（占用 {u、e}）。它和当前已选 空串 没有公共字母，按位与为 0，可以选入。
合法 · "ue"：当前已串联 "ue"，长度 2，字母互不相同，是一个合法组合。用它刷新最大长度，目前最大长度 = 4。
回溯 · 撤销 "ue"：选入 "ue" 的所有后续分支都试完了，回溯：把它从组合里撤掉，当前累计指纹和长度恢复成选它之前的 空串，再去试下一个候选。
完成 · 最大长度 4：决策树全部走完。所有合法组合里最长的是 "uniq"（"un"+"iq"）或 "ique"（"iq"+"ue"），长度都是 4，这就是最终答案。
边界先想清：所有串都自身重复时答案是 0（空串）；互不冲突时可以全选；最长不超过 26（字母总数）。
面试可延伸：bitmask 相比哈希集合的速度与空间优势，以及约束如何天然排除重复选。
参考代码
from typing import Listclass Solution: def maxLength(self, arr: List[str]) -> int: masks = [] for s in arr: mask = 0 ok = True for ch in s: bit = 1 << (ord(ch) - 97) if mask & bit: ok = False; break mask |= bit if ok: masks.append((mask, len(s))) ans = 0 def dfs(i, mask, length): nonlocal ans ans = max(ans, length) for j in range(i, len(masks)): m, l = masks[j] if mask & m == 0: dfs(j + 1, mask | m, length + l) dfs(0, 0, 0) return ans复杂度
- 时间：O(2^n)，n 为合法候选串个数；每个串选或不选，决策树最多 2^n 个状态，剪枝后通常远小于此
- 空间：O(n)，递归栈深最多 n 层；mask 是单个整数 O(1)，存指纹列表 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么用整数 bitmask 而不是用哈希集合表示字母占用？
追问如果改成可以重复选同一个串呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出不同的二进制字符串
LeetCode 1980 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题