题目
给你一个只包含小写字母的字符串 s，你需要找到 s 中最多数目的非空子字符串，满足如下条件：
- 这些字符串之间互不重叠。也就是说对于任意两个子字符串
s[i..j]和s[x..y]，要么j < x，要么i > y。 - 如果一个子字符串包含字符
char，那么s中所有char字符都应该在这个子字符串中。
请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。
请注意，你可以以任意顺序返回最优解的子字符串。
题目分析
先把两个条件翻译成人话
条件 2 是最关键、也最容易被忽略的一句。 它说的是：你不能"只要一部分"。比如 s 里有三个 a，那么任何一个包含 a 的子串，必须把这三个 a 全部包进去。
这句话有一个很强的推论：
每个字符一旦被占用，它绑定的区间就被钉死了，只能往外扩，不能往里缩。
也就是说，“能选的区间"不是随便取的，而是由字符串本身唯一决定的。我们真正的自由度只剩一条：在这些固定区间里挑几个互不重叠的。
第一步：先看每个字符的"势力范围”
拿题目的例子说：
s = "adefaddaccc"
下标 0 1 2 3 4 5 6 7 8 9 10
字符 a d e f a d d a c c c
先不管条件 2，只看"第一次出现"和"最后一次出现"，得到每个字符的原始区间：
| 字符 | 首次出现 | 末次出现 | 原始区间 |
|---|---|---|---|
a |
0 | 7 | [0,7] |
d |
1 | 6 | [1,6] |
e |
2 | 2 | [2,2] |
f |
3 | 3 | [3,3] |
c |
8 | 10 | [8,10] |
第二步：原始区间还不够，得"扩张"
看一下 d：它的原始区间是 [1,6]，而 s[1..6] = "defadd"。这里面有 a！
根据条件 2，既然这个子串包含了 a，就必须把 s 里所有的 a 都包进来。而 a 最右边的一个出现在下标 7，所以 d 的区间被迫从 [1,6] 扩成 [1,7]。
扩张之后又冒出新麻烦：现在的 [1,7] 里有下标 7 那个 a，而 a 最左边的一个出现在下标 0，于是再往左扩到 0。
最终 d 的区间变成 [0,7]——和 a 一模一样。
💡 这就叫"闭包"。 从原始区间出发，把区间内所有字符的区间都并进来，一直并到"再也并不出新东西"为止。形象点说就是"一个人拉一群人，一群人又拉更多人"，直到没人可拉。
相比之下，a 自己的区间 [0,7] 里只有 d、e、f，它们都落在 [0,7] 内部，所以 a 一轮就稳定了，不用扩。
第三步：得到所有候选区间并去重
a: [0,7]
d: [0,7] ← 和 a 撞了
e: [2,2]
f: [3,3]
c: [8,10]
a 和 d 的区间完全相同。两个一样的区间，选了 a 就不可能再选 d（它们必然重叠），而且它们覆盖的范围也完全一样，所以留着没有任何额外收益，直接去重：
候选区间: [0,7] [2,2] [3,3] [8,10]
第四步：问题退化成"最多不重叠区间"
把四个候选区间摊到数轴上：
| 区间 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
[0,7] |
● | ● | ● | ● | ● | ● | ● | ● | |||
[2,2] |
● | ||||||||||
[3,3] |
● | ||||||||||
[8,10] |
● | ● | ● |
现在一眼能看出三件事：
[0,7]和[2,2]、[3,3]重叠（2、3 都落在 0~7 里），不能同时选。[0,7]和[8,10]不重叠（7 < 8）。[2,2]、[3,3]、[8,10]三者互不重叠。
于是可能的方案只剩两种：
| 方案 | 选中的区间 | 数量 | 总长度 |
|---|---|---|---|
| A | [2,2]、[3,3]、[8,10] |
3 | 1+1+3 = 5 |
| B | [0,7]、[8,10] |
2 | 8+3 = 11 |
方案 A 数量更多，所以答案是方案 A，输出 "e"、"f"、"ccc"。
小结：题目其实只剩两件事
这个例子里数量就分出了胜负，根本轮不到比长度。这是因为题目给的两个目标有明确的优先级：
先比数量（要最多），数量相同时才比总长度（要最小）。
所以后面的算法必须严格按这个优先级来比较——这一点在后面的 DP 里会真正派上用场。
算法分析
整体流程
| 步骤 | 做什么 | 复杂度 |
|---|---|---|
| 1 | 扫描一遍，记录每个字母的首次/末次出现 | $O(n)$ |
| 2 | 闭包扩张，得到每个字母的最小自包含区间 | $O(26^2 n)$ |
| 3 | 去重 | $O(26^2)$ |
| 4 | 区间 DP，挑出最多的不重叠区间 | $O(26^2)$ |
| 5 | 按选中的区间截取子串 | $O(26n)$ |
因为只有 26 个小写字母，候选区间最多 26 个，所以第 3、4 步的开销可以忽略。
下面全程用这个更简单、但**同样能体现"长度比较"**的字符串来演示：
s = "abbaccd"
下标 0 1 2 3 4 5 6
字符 a b b a c c d
第 1 步：扫描一遍，记录首次/末次出现
开两个数组：
left[c]= 字母c第一次出现的位置right[c]= 字母c最后一次出现的位置
vector<int> left(26, n), right(26, -1); // left 初始为"最大"，right 初始为"最小"
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
left[c] = min(left[c], i); // 遇到更小的位置就更新
right[c] = max(right[c], i); // 遇到更大的位置就更新
}
💡 用
min/max连续"收敛"，就不用额外写if (第一次遇到)这类判断了。
对 "abbaccd" 跑一遍：a 出现在 0 和 3 → [0,3]；b 出现在 1 和 2 → [1,2]；c 出现在 4 和 5 → [4,5]；d 只在 6 出现 → [6,6]。
a:[0,3] b:[1,2] c:[4,5] d:[6,6]
第 2 步：闭包扩张——把区间"撑"到自包含
对每个出现过的字母 c，从 [left[c], right[c]] 出发，反复执行同一件事：
区间内出现了哪些字母，就把这些字母的完整区间也并进来。
写成代码就是不断把 start 往左推、把 end 往右推，直到某一轮完全没有任何变化才停：
int start = left[c], end = right[c];
bool changed = true;
while (changed) {
changed = false; // 假设这一轮不会变
for (int i = start; i <= end; i++) {
int x = s[i] - 'a'; // 区间里圈到了字母 x
if (left[x] < start) { start = left[x]; changed = true; } // x 左边还有 → 左边界左移
if (right[x] > end) { end = right[x]; changed = true; } // x 右边还有 → 右边界右移
}
} // 一轮下来没变过 = 收敛，退出
为什么一定要"反复扫"，扫一轮不够？
因为扩张本身会带进新字符：
第一轮：区间 [l, r] 里发现了字母 x
→ x 在 r 右边还有 → 区间变成 [l, r'] (r' > r)
第二轮：新扩进来的 [r+1, r'] 里可能又冒出新字母 y
→ y 又要求往两边扩
第三轮：…… 直到某一轮一次都没变
这就是不动点迭代：从原始区间出发，反复应用同一条规则，直到结果不再改变。
在本题例子上走一遍：
a 从 [0,3] 出发：区间里圈到 b，b 要求 [1,2]，已被包含 → 不用扩 → 最终 [0,3]
b 从 [1,2] 出发：区间里只有 b → 不用扩 → 最终 [1,2]
c 从 [4,5] 出发：区间里只有 c → 不用扩 → 最终 [4,5]
d 从 [6,6] 出发：区间里只有 d → 不用扩 → 最终 [6,6]
这个例子里四个字母的区间互不纠缠，一轮就收敛了。对比 adefaddaccc 里的 d：[1,6] → 圈到 a → 被迫扩到 [0,7]，那才是"扩张"真正发威的样子。
第 3 步：去重
闭包算完，手上最多 26 个区间，把它们两两比较，完全相同的只留一个：
vector<pair<int,int>> cand;
for (int c = 0; c < 26; c++) {
if (subs[c].first < 0) continue; // 这个字母压根没出现过
bool dup = false;
for (auto& t : cand)
if (t == subs[c]) { dup = true; break; }
if (!dup) cand.push_back(subs[c]);
}
本例 4 个区间互不相同，全部保留：
[1,2] [0,3] [4,5] [6,6]
第 4 步：区间 DP——挑出最多的不重叠区间
① 先按右端点从小到大排序
[1,2] [0,3] [4,5] [6,6]
为什么按右端点排，而不是左端点？因为判断"两个区间是否重叠"只需要看右端点：区间 j 完全在区间 i 左边 ⟺ end[j] < start[i]。按右端点排好之后，这个判断只要往前看就够了，最省事。
② 定义状态
dp[i] = 在排好序的区间里，一定选第 i 个区间时能得到的最优解 (个数, 总长度)
初始 dp[i] = (1, 第 i 个区间自己的长度) ← 最差也比什么都不选强
③ 转移
枚举所有排在 i 前面、且和 i 不重叠的 j，看看"接在 j 后面"是不是更划算：
对每个 j < i 且 end[j] < start[i]：
dp[i] = dp[i] 与 (dp[j].个数 + 1, dp[j].总长 + 区间i的长度) 中的更优者
这里的"更优"不是简单的数值大小，而是题目规定的优先级：
个数多的赢；个数一样多时，总长小的赢。
// 判断方案 A 是否优于方案 B
bool better(pair<int,int>& A, pair<int,int>& B) {
if (A.first != B.first) return A.first > B.first; // 先比个数：多的赢
return A.second < B.second; // 个数相同，再比总长：小的赢
}
④ 逐格填表（本例）
| 区间 | 能接在谁后面 | dp 值 | 对应子串 |
|---|---|---|---|
[1,2] |
没有 end < 1 的区间 |
(1, 2) |
"bb" |
[0,3] |
没有 end < 0 的区间 |
(1, 4) |
"abba" |
[4,5] |
接 [1,2] 得 (2, 4)；接 [0,3] 得 (2, 6) |
(2, 4) |
"bb" + "cc" |
[6,6] |
接 [4,5] 得 (2+1, 4+1) |
(3, 5) |
"bb"+"cc"+"d" |
这里就是本题最精彩的一步。 处理 [4,5] 时，两种接法的个数都是 2，数量维度打平了，于是必须动用量长度这一招：
接 [1,2] ："bb" + "cc" → 总长 2 + 2 = 4 ✅ 更短，选它
接 [0,3] ："abba" + "cc" → 总长 4 + 2 = 6 ❌ 更长，淘汰
如果没有长度比较，随手留下先遇到的那个，就可能得到 "abba"+"cc"+"d"（总长 7），而不是最优的 "bb"+"cc"+"d"（总长 5）。
⚠️ 两个比较维度缺一不可，而且顺序不能反。 如果反过来"先比长度"，就会倾向于挑一堆超短的区间，很可能把"能选 3 个"的方案压成"只选 1 个很短但数量更少"的方案——数量直接就错了。
⑤ 为什么这样 DP 是对的？
所有区间按右端点排序后，“选哪些区间"就变成了一个从左往右的决策序列：要么不选当前区间，要么选它、并把它接在某个更靠左的区间后面。
而 dp[i] 正好把”以 i 结尾的最优解"完整记录了下来，所以后面任何区间想接在 i 后面时，直接用 dp[i] 就够了，完全不用回头重新考虑 i 之前的选择——这就是最优子结构。
第 5 步：回溯出具体方案
光有 dp 里的数字不够，题目要的是具体哪几个子串。所以填表时顺手记一笔"我是从谁转移过来的"：
vector<int> pre(m, -1); // pre[i] = dp[i] 是从哪个 j 接上来的；-1 表示没有前驱
最后找出全局最优秀的 best，沿着 pre 链一路往前回溯：
[6,6] ← [4,5] ← [1,2]
再把每个区间还原成子串：
ans.push_back( s.substr(start, end - start + 1) );
本例选中的是 [1,2]、[4,5]、[6,6]，对应：
"bb" "cc" "d" // 3 个子串，总长 5
📌 回溯是从右往左走的，所以实际输出顺序是
"d" "cc" "bb"。题目明确允许任意顺序，两种写法都对。
关于 dp 的两种常见写法
你可能在别处见过 dp[i] 被定义成另一个意思：
| 写法 | dp[i] 的含义 |
最后答案怎么取 |
|---|---|---|
| 本文 | 一定选第 i 个区间时的最优 |
扫一遍取全局最大 |
| 另一种 | 在前 i 个区间里随便选（可以跳过第 i 个）时的最优 |
直接取 dp[m] |
第二种写法的转移里多一个分支：dp[i] = dp[i-1]，表示"跳过第 i 个"。两者都能算出正确答案，只是中间记录的数值不同。
举个能看出差别的例子：s = "bacca"，候选区间是 [0,0]、[2,3]、[1,4]（已按右端点排好）。
"一定选第 i 个" "前 i 个随便选"
dp[0] [0,0] (1, 1) (1, 1)
dp[1] [2,3] (2, 3) (2, 3)
dp[2] [1,4] (2, 5) ← 选了它自己 (2, 3) ← 跳过它，沿用 dp[1]
最终答案：数量 2，总长 3（也就是 "b" + "cc"）
dp[2] 的数值不一样，但最终答案完全一致。这两种定义只影响代码怎么写，不影响结果。
复杂度
- 第 1 步：扫一遍字符串，$O(n)$。
- 第 2 步：最费时的部分。为什么
while一定能停下来？左边界只会往左移，而且每移一次都会停在某个字母的首次出现位置上——这样的位置最多 26 个；同理右边界最多调整 26 次。所以循环最多约 50 轮，每轮扫一遍当前区间。单个字母 $O(26n)$，26 个字母合计 $O(26^2 n)$。 - 第 3、4 步：候选区间最多 26 个，$O(26^2)$，可以忽略。
- 第 5 步：截取子串，$O(26 \cdot n)$。
总额 $O(26^2 n)$。虽然在 $n = 10^4$ 时这是个"上界很宽松"的估计（约 676 万），但实际跑下来每个字符也就几轮就收敛了，实测约 0.7 ms，$n \le 10^4$ 完全无压力。
💡 顺带一提，如果
while没有"某一轮没变化就退出"这个条件，代码就会死循环——因为区间已经收敛了，但循环还在跑。这个退出条件不是优化，是正确性的一部分。
代码演示
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 判断方案 A 是否优于方案 B：个数多者赢；个数相同，总长小者赢
bool better(pair<int,int>& A, pair<int,int>& B) {
if (A.first != B.first) return A.first > B.first; // 先比个数
return A.second < B.second; // 再比总长
}
vector<string> maxNumOfSubstrings(string s) {
int n = s.size();
// ---------- 第 1 步：扫描一遍，记录每个字母的首次/末次出现 ----------
vector<int> left(26, n), right(26, -1);
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
left[c] = min(left[c], i);
right[c] = max(right[c], i);
}
// ---------- 第 2 步：闭包扩张 ----------
// subs[c] = {start, end}：字母 c 的最小自包含区间（区间内所有字母都被完整包住）
vector<pair<int,int>> subs(26, {-1, -1});
for (int c = 0; c < 26; c++) {
if (right[c] < 0) continue; // 这个字母没出现过
int start = left[c], end = right[c];
bool changed = true;
while (changed) { // 反复扫，直到某一轮完全没变化
changed = false;
for (int i = start; i <= end; i++) {
int x = s[i] - 'a'; // 区间里圈到了字母 x
if (left[x] < start) { start = left[x]; changed = true; }
if (right[x] > end) { end = right[x]; changed = true; }
}
}
subs[c] = {start, end};
}
// ---------- 第 3 步：去重（区间完全相同的只留一个） ----------
vector<pair<int,int>> cand;
for (int c = 0; c < 26; c++) {
if (subs[c].first < 0) continue;
bool dup = false;
for (auto& t : cand)
if (t == subs[c]) { dup = true; break; }
if (!dup) cand.push_back(subs[c]);
}
// ---------- 第 4 步：按右端点排序 + 区间 DP ----------
sort(cand.begin(), cand.end(),
[](const pair<int,int>& a, const pair<int,int>& b) {
return a.second < b.second; // 右端点小的排前面
});
int m = cand.size();
if (m == 0) return {}; // 空串的边界情况
vector<pair<int,int>> dp(m); // dp[i] = (个数, 总长)
vector<int> pre(m, -1); // pre[i] = 转移来源，用于回溯
for (int i = 0; i < m; i++) {
int len = cand[i].second - cand[i].first + 1;
dp[i] = {1, len}; // 最差也能只选自己
for (int j = 0; j < i; j++) {
if (cand[j].second < cand[i].first) { // j 完全在 i 左边 → 不重叠
pair<int,int> cur = {dp[j].first + 1, // 个数 +1
dp[j].second + len}; // 总长加上自己
if (better(cur, dp[i])) {
dp[i] = cur;
pre[i] = j; // 记住是从 j 接过来的
}
}
}
}
// 找全局最优秀的那个状态
int best = 0;
for (int i = 1; i < m; i++)
if (better(dp[i], dp[best])) best = i;
// ---------- 第 5 步：沿 pre 链回溯，截出子串 ----------
vector<string> ans;
for (int i = best; i != -1; i = pre[i])
ans.push_back(s.substr(cand[i].first,
cand[i].second - cand[i].first + 1));
return ans; // 顺序任意，题目允许
}
int main() {
// 测试 1：adefaddaccc → 数量 3，直接分出胜负
// 测试 2：abbaccd → 数量打平，靠总长比较定下方案
for (string s : {"adefaddaccc", "abbaccd"}) {
cout << s << " -> ";
for (auto& t : maxNumOfSubstrings(s)) cout << "\"" << t << "\" ";
cout << endl;
}
return 0;
}
运行结果：
adefaddaccc -> "ccc" "f" "e"
abbaccd -> "d" "cc" "bb"
（题目允许以任意顺序返回，所以这里从右往左的输出同样正确。第一组数量为 3，直接分出胜负；第二组数量打平，靠总长度比较定下 "bb" "cc" "d"。）