从「无重叠区间」到 LeetCode 1520：一次完整的算法踩坑与优化记录

本文记录我从 LeetCode 435（无重叠区间）出发，一路做到 LeetCode 1520（最多的不重叠子字符串）的完整过程：从贪心的两种解法，到套错框架、TLE、修超时、再优化，最后对比官解。适合想理清「区间调度 + 字符串扩展」这类题的读者。

一、先聊「无重叠区间」的两种解法

LeetCode 435 是这类问题的起点：给一堆区间，问最少删掉几个，使剩下的互不重叠。

它有两个经典解法。

解法 1：动态规划（LIS 式）

按左端点排序，定义：

f[i] = 以第 i 个区间结尾的最长不重叠区间链长度

转移：

f[i] = max(f[i], f[j] + 1) 当 intervals[j][1] <= intervals[i][0]

答案：

n – max(f)

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}

sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[0] < v[0];
});

int n = intervals.size();
vector<int> f(n, 1);//dpf[i] = 在排序后的前 i+1 个区间中，必须包含第 i 个区间，且这些区间两两不重叠的情况下，最多能选多少个区间
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (intervals[j][1] <= intervals[i][0]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
return n – *max_element(f.begin(), f.end());
}
};

这个 DP 结构就是「区间版的最长上升子序列」。正确，但 O(n²)。

解法 2：贪心（按右端点排序）

按右端点升序排序；
从左到右扫，若当前区间左端点 > 已选区间右端点，就选它。

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size()==1)return 0;
sort(intervals.begin(),intervals.end(),[](const vector<int>& a,const vector<int>&b){
return a[0]<b[0];
});
int r=INT_MIN,sum=0;
for(auto a:intervals){
if(a[0]>=r){
r=a[1];
}else{
if(a[1]<r){
r=a[1];
}
sum++;
}

}
return sum;
}
};

这是区间调度的经典贪心，O(n log n)，最优。

两者对比

435 是无权版本，所以正解是贪心。这一点，是我后面踩坑的伏笔。

二、引入 LeetCode 1520：最多的不重叠子字符串

题目大意：

给你一个字符串 s，找出最多的不重叠子串，要求每个子串都包含其内部所有字符的全部出现。

例如 s = "adefaddaccc"，答案是 ["e","f","ccc"]。

这题和 435 的关系：

• 435 是"给区间，选最多不重叠"；

• 1520 是"先构造合法区间，再选最多不重叠，最后返回子串"。

也就是说，1520 = 区间构造（扩展）+ 435 的无权贪心。

三、我的第一版：套用了 435 的"最少删除"框架

一开始，我写出来的代码长这样（简化）：

class Solution { //没有考虑到扩展情况"abab"
public:

vector<string> maxNumOfSubstrings(string s) {
auto cut = [&](int l, int r) {
return s.substr(l, r – l + 1);
};
unordered_map<char,vector<int>>mp;
vector<vector<int>>mmap;
for(auto a:s){
if(!mp.count(a)){
int b=s.find(a);
int c=s.rfind(a);
mp[a]={b,c};
mmap.push_back({b,c});//！！！！这里！没有扩展！
}
}
sort(mmap.begin(),mmap.end(),[](const vector<int>& a,const vector<int>&b){
return a[0]<b[0];
});
int r=INT_MIN,sum=0;int l;
for(auto a:mmap){
if(a[0]>=r){
r=a[1];
l=a[0];
}else{
if(a[1]<r){
r=a[1];
mp.erase(s[l]);
l=a[0];
}else{
mp.erase(s[a[0]]);
}
}
}
vector<string>result;
for(auto a:mp){
result.push_back(cut(a.second[0],a.second[1]));
}
return result;
}
};

这段代码错在哪

四、第二版：加上扩展区间，但超时了

为了修"没扩展"的问题，我加了一段：

bool changed = true;
while (changed) {
changed = false;
for (int i = b; i <= c; ++i) {
char ch = s[i];
int nf = s.find(ch); // O(n)
int nl = s.rfind(ch); // O(n)
if (nf < b) { b = nf; changed = true; }
if (nl > c) { c = nl; changed = true; }
}
}

逻辑是对的，但超时。

class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
auto cut = [&](int l, int r) {
return s.substr(l, r – l + 1);
};

unordered_map<char, vector<int>> mp;
vector<vector<int>> mmap;

for (auto a : s) {
if (!mp.count(a)) {
int d=s.find(a);
int b = s.find(a);
int c = s.rfind(a);
// ↓↓↓ 新增：扩展区间直到稳定 ↓↓↓
bool changed = true;
while (changed) {
changed = false;
for (int i = b; i <= c; ++i) {
char ch = s[i];
int nf = s.find(ch);
int nl = s.rfind(ch);
if (nf < b) { b = nf; changed = true; }
if (nl > c) { c = nl; changed = true; }
}
}
// ↑↑↑ 新增结束 ↑↑↑
mp[a] = {b, c};
mmap.push_back({b,c,d});//因为扩展了，导致扩展的头可能不是要删除的头，于是多加一个元素放真正的头！！！！！！！！！！！
}
}

sort(mmap.begin(), mmap.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});

int r = INT_MIN, sum = 0;
int l;
for (auto a : mmap) {
if (a[0] >= r) {
r = a[1];
l = a[2];
} else {
if (a[1] < r) {
r = a[1];
mp.erase(s[l]);
l = a[2];
} else {
mp.erase(s[a[2]]);
}
}
}

vector<string> result;
for (auto a : mp) {
result.push_back(cut(a.second[0], a.second[1]));
}
return result;
}
};

超时原因

• 外层 while(changed) 最坏扩展 O(n) 次；

• 内层 for 是 O(n)；

• 每次 s.find/rfind 又是 O(n)。

单个字符最坏 O(n³)，26 个字符总最坏 O(26·n³)。n = 10⁵ 时是 10¹⁵ 量级，必然 TLE。

根因

把 find/rfind 这种 O(n) 操作，嵌套在了双层循环里。

五、第三版：修超时，把 find/rfind 换成数组

思路很简单：预处理每个字符的首末位置，把 O(n) 查询变成 O(1)。

int n = s.size();
vector<int> first(26, n), last(26, -1);
for (int i = 0; i < n; ++i) {
int c = s[i] – 'a';
first[c] = min(first[c], i);
last[c] = max(last[c], i);
}

扩展时：

bool changed = true;
while (changed) {
changed = false;
for (int i = b; i <= c; ++i) {
int ch = s[i] – 'a';
if (first[ch] < b) { b = first[ch]; changed = true; }
if (last[ch] > c) { c = last[ch]; changed = true; }
}
}

这一版不超时了，"adefaddaccc" 也能输出 ["e","f","ccc"]

class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
int n = s.size();
vector<int> first(26, n), last(26, -1);//修超时：把 find/rfind 换成数组
for (int i = 0; i < n; ++i) {
int c = s[i] – 'a';
first[c] = min(first[c], i);
last[c] = max(last[c], i);
}

auto cut = [&](int l, int r) {
return s.substr(l, r – l + 1);
};

unordered_map<char, vector<int>> mp;
vector<vector<int>> mmap;

for (auto a : s) {
if (!mp.count(a)) {
int d = first[a – 'a']; // 原始首位置
int b = first[a – 'a'];
int c = last[a – 'a'];
bool changed = true;
while (changed) {
changed = false;
for (int i = b; i <= c; ++i) {
int ch = s[i] – 'a';
if (first[ch] < b) { b = first[ch]; changed = true; }
if (last[ch] > c) { c = last[ch]; changed = true; }
}
}
mp[a] = {b, c};
mmap.push_back({b, c, d});
}
}

sort(mmap.begin(), mmap.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});

int r = INT_MIN;
int l = 0;
for (auto a : mmap) {
if (a[0] >= r) {
r = a[1];
l = a[2];
} else {
if (a[1] < r) {
r = a[1];
mp.erase(s[l]);
l = a[2];
} else {
mp.erase(s[a[2]]);
}
}
}

vector<string> result;
for (auto a : mp) {
result.push_back(cut(a.second[0], a.second[1]));
}
return result;
}
};

但仍有隐患

• 扩展最坏还是 O(26·n²)（while 反复扫）；

• 贪心仍是"按左端点排序 + erase 反悔"，不保证最优；

• 结果从 unordered_map 输出，顺序随机。

也就是说：复杂度勉强过，但正确性靠用例运气。

六、第四版：单次扫描扩展 + 标准贪心

真正的优化，要把两件事一起做对。

优化 1：扩展从 while(changed) 改成单次扫描

关键观察：右边界 c 只增不减，所以从左到右扫一遍即可，扫过的新区域会自动被覆盖。

int b = first[c], e = last[c];
bool valid = true;
for (int i = b; i <= e; ++i) { // e 在循环中会增大
int ch = s[i] – 'a';
if (first[ch] < b) { valid = false; break; } // 区间外还有该字符 → 非法
if (last[ch] > e) e = last[ch]; // 扩右边界
}

• 复杂度从 O(n²) 降到 O(n)（每个字符）；

• first[ch] < b 提前 break，剪掉大量非法区间。

优化 2：贪心改成标准写法

sort(intervals.begin(), intervals.end(),
[](auto& a, auto& b) { return a.second < b.second; }); // 按右端点

vector<string> res;
int end = -1;
for (auto& [b, e] : intervals) {
if (b > end) { // 不重叠 → 选
res.push_back(s.substr(b, e – b + 1));
end = e;
}
}

• 按右端点排序；

• 不重叠就选，选中立即收集；

• 不再 erase，不再遍历 unordered_map。

第四版完整代码

class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
int n = s.size();
vector<int> first(26, n), last(26, -1);
for (int i = 0; i < n; ++i) {
int c = s[i] – 'a';
first[c] = min(first[c], i);
last[c] = max(last[c], i);
}

vector<pair<int,int>> intervals;
for (int c = 0; c < 26; ++c) {
if (last[c] == -1) continue;
int b = first[c], e = last[c];
bool valid = true;
for (int i = b; i <= e; ++i) {
int ch = s[i] – 'a';
if (first[ch] < b) { valid = false; break; }
if (last[ch] > e) e = last[ch];
}
if (valid) intervals.push_back({b, e});
}

sort(intervals.begin(), intervals.end(),
[](const auto& a, const auto& b) { return a.second < b.second; });

vector<string> res;
int end = -1;
for (auto& [b, e] : intervals) {
if (b > end) {
res.push_back(s.substr(b, e – b + 1));
end = e;
}
}
return res;
}
};

优化前后对比

七、官解分析：双指针向两侧扩散

整体思路：两步走

官解的结构非常清晰，就两大块：

1. 构造所有"合法区间" → pos + 双指针扩展
2. 从合法区间里选最多不重叠 → 按右端点排序 + 贪心

这正好对应题目里的两个难点：

第一步：记录每个字符的首末位置

unordered_map<char, pair<int, int>> pos;
for (int i = 0; i < s.length(); i++) {
char ch = s[i];
if (pos.find(ch) == pos.end()) {
pos[ch] = {i, i};
} else {
pos[ch].second = i;
}
}

• pos[ch] = {第一次出现, 最后一次出现}；

• 遍历一次 O(n)；

• 用 unordered_map 而不是 26 数组，字符集不限于小写字母时也通用。

这一步是后面所有扩展的查询表。

第二步（核心）：双指针向两侧扩散

这是整份官解最精彩的部分。

for (auto& [c, range] : pos) {
int l = range.first, r = range.second;
int nl = l, nr = l;

while (nl >= l || nr <= r) {
int i = (nl >= l) ? nl : nr;

int l_t = pos[s[i]].first;
int r_t = pos[s[i]].second;

if (l_t < l) l = l_t; // 向左扩
if (r_t > r) r = r_t; // 向右扩

if (i == nl) nl–;
if (i == nr) nr++;
}

valid.push_back({l, r});
}

 它在干什么

对每个字符 c，从它的初始区间 [l, r] 出发：

• nl：左指针，从 l 开始往左走；

• nr：右指针，从 l 开始往右走；

• 每次取一个指针位置的字符 s[i]，查它的首末 [l_t, r_t]：

  • 若 l_t < l，说明这个字符在更左边也出现过，左边界必须扩到 l_t；

  • 若 r_t > r，说明它在更右边也出现过，右边界必须扩到 r_t；

• 扩完后继续检查新纳入的字符，直到两个指针都走出当前区间。

为什么是"向两侧"而不是"扫内部"

常见写法是扫区间内部：

for (int i = b; i <= e; ++i) { … } // e 动态增大

官解换了个视角：检查区间外的字符，发现漏掉就扩过去。

两种视角等价，但官解更贴合题目的语义——"子串必须包含内部字符的全部出现"，反过来说就是"不能有字符在区间外还有出现"。双指针就是去验证这一点。

 while 的条件为什么是 nl >= l || nr <= r

• nl >= l：左指针还在区间内，还有字符没检查；

• nr <= r：右指针还在区间内，还有字符没检查；

• 只要任意一个还在区间内，就继续。

注意 nl 和 nr 都从 l 出发，所以一开始两边都在区间内。

指针移动的细节

if (i == nl) nl–;
if (i == nr) nr++;

• 如果这次处理的是左指针位置，左指针就左移一格；

• 如果是右指针位置，右指针就右移一格；

• 两个 if 分开写，是因为 i 可能同时等于 nl 和 nr（初始时 nl = nr = l），此时两边都要动。

为什么结束时区间一定合法

• 区间被扩展后，新纳入的字符会被继续检查；

• 直到所有在区间内的字符，其全部出现都落在区间内；

• 所以最终区间必然满足"包含内部所有字符的全部出现"。

第三步：按右端点排序 + 贪心

sort(valid.begin(), valid.end(),
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
});

vector<string> ans;
int end = -1;
for (auto& [left, right] : valid) {
if (left > end) {
ans.push_back(s.substr(left, right – left + 1));
end = right;
}
}

这是经典的区间调度贪心：

• 按右端点升序；

• left > end 说明与已选区间不重叠，选它，更新 end = right；

• 否则跳过；

• 选中时立即收集子串，结果天然有序。

为什么按右端点？

右端点越小，留给后面的空间越大。按右端点排序后，每次选"最早结束且不重叠"的区间，能选出最多数量——这是区间调度问题的经典结论，可用交换论证证明。

官解的精髓，可以浓缩成两句话：

扩展区间：用双指针向两侧扩散，直到区间包含内部所有字符的全部出现。
选择区间：按右端点排序，贪心选最多不重叠区间，选中即收集。

它把一道看起来复杂的字符串题，干净地拆成了"构造 + 调度"两个经典子问题。这种把新问题归约到已知模型的能力，正是算法题最值得学习的地方。

附：官解代码（带注释）

class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
// 1. 记录每个字符的第一次和最后一次出现位置
unordered_map<char, pair<int, int>> pos;
for (int i = 0; i < s.length(); i++) {
char ch = s[i];
if (pos.find(ch) == pos.end()) {
pos[ch] = {i, i};
} else {
pos[ch].second = i;
}
}

// 2. 双指针向两侧扩散，构造所有合法区间
vector<pair<int, int>> valid;
for (auto& [c, range] : pos) {
int l = range.first, r = range.second;
int nl = l, nr = l;

while (nl >= l || nr <= r) {
int i = (nl >= l) ? nl : nr;

int l_t = pos[s[i]].first;
int r_t = pos[s[i]].second;

if (l_t < l) l = l_t; // 向左扩
if (r_t > r) r = r_t; // 向右扩

if (i == nl) nl–;
if (i == nr) nr++;
}

valid.push_back({l, r});
}

// 3. 按右端点升序排序
sort(valid.begin(), valid.end(),
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
});

// 4. 贪心选择互不重叠的区间
vector<string> ans;
int end = -1;
for (auto& [left, right] : valid) {
if (left > end) {
ans.push_back(s.substr(left, right – left + 1));
end = right;
}
}

return ans;
}
};

一句话：官解 = 双指针扩展合法区间 + 按右端点贪心选最多不重叠，O(n) 级，清晰且可证明最优。