作者推荐
视频算法专题
本身涉及知识点
解析几何 图论 多源路径 贪心
LeetCode1520. 最多的不重叠子字符串
给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：
这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i…j] 和 s[x…y] ，要么 j < x 要么 i > y 。
如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中。
请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。
请注意，你可以以 任意 顺序返回最优解的子字符串。
示例 1：
输入：s = “adefaddaccc”
输出：[“e”,“f”,“ccc”]
解释：下面为所有满足第二个条件的子字符串：
[
“adefaddaccc”
“adefadda”,
“ef”,
“e”,
“f”,
“ccc”,
]
如果我们选择第一个字符串，那么我们无法再选择其他任何字符串，所以答案为 1 。如果我们选择 “adefadda” ，剩下子字符串中我们只可以选择 “ccc” ，它是唯一不重叠的子字符串，所以答案为 2 。同时我们可以发现，选择 “ef” 不是最优的，因为它可以被拆分成 2 个子字符串。所以最优解是选择 [“e”,“f”,“ccc”] ，答案为 3 。不存在别的相同数目子字符串解。
示例 2：
输入：s = “abbaccd”
输出：[“d”,“bb”,“cc”]
解释：注意到解 [“d”,“abba”,“cc”] 答案也为 3 ，但它不是最优解，因为它的总长度更长。
提示：
1 <= s.length <= 105
s 只包含小写英文字母。
分析
{ 如果一个子字符串包含字符 c h a r ，那么 s 中所有 c h a r 字符都应该在这个子字符串中。简称条件一。 子串（非子序列 ) 如果某个子串包括 c 1 ，则包括所有 c 1 和之间所有字符。 \begin{cases} 如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中。 简称条件一。\\ 子串（非子序列)\\ \end{cases} 如果某个子串包括c1，则包括所有c1和之间所有字符。 {如果一个子字符串包含字符char，那么s中所有char字符都应该在这个子字符串中。简称条件一。子串（非子序列)如果某个子串包括c1，则包括所有c1和之间所有字符。
多源路径
26个字符看成26个节点，如果字符c1之间有字符c2，则有有向边 c 1 c 2 → \overrightarrow{c1c2} c1c2。利用多源路径看c1到c3是否存在，如果存在则选择c1时，c3也必须选择。令选择c1后，至少选择[l1,r1]。
解析几何
把[i1,r1]看线段，求最多不相交的线段。
贪心
第一条线段，一定是ri最小的，令为t1，显然越小，第二条线越容易找。
第二条线段，一定是ri最小，且li大于t1的。
⋮
\vdots
⋮
线段不会交叉，只能包括或相离。所以ri小的，就短。
令a<b<c<d，假定线段：ac和bd相交与bc。
ab中一定有bc中的某个字符，假定其小标为i1，否则ac不会包括bc。bd包括bc，故有此字符，bd必须包括i1，与假设矛盾。
代码
核心代码
//多源码路径
template<class T, T INF = 1000 * 1000 * 1000>
class CFloyd
{
public:
CFloyd(const vector<vector<T>>& mat)
{
m_vMat = mat;
const int n = mat.size();
for (int i = 0; i < n; i++)
{//通过i中转
for (int i1 = 0; i1 < n; i1++)
{
for (int i2 = 0; i2 < n; i2++)
{
//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
}
}
}
};
vector<vector<T>> m_vMat;
};
template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
*seft = min(*seft,(ELE) other);
}
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
*seft = max(*seft, other);
}
class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
vector<int> indexs[26];
for (int i = 0; i < s.length(); i++)
{
indexs[s[i] - 'a'].emplace_back(i);
}
vector<vector<int>> mat(26, vector<int>(26,1000'000'000));
for (int i = 0; i < 26; i++)
{
if (indexs[i].empty()) { continue; }
for (int j = 0; j < 26; j++)
{
auto it1 = std::lower_bound(indexs[j].begin(), indexs[j].end(), indexs[i].front());
auto it2 = std::upper_bound(indexs[j].begin(), indexs[j].end(), indexs[i].back());
if (it2 - it1 > 0 )
{
mat[i][j] = 1;
}
}
}
CFloyd floyd(mat);
vector<pair<int, int>> rl;
for (int i = 0; i < 26; i++)
{
int left = 1000'000, r = -1;
for (int j = 0; j < 26; j++)
{
if (floyd.m_vMat[i][j] < 1000'000'000)
{
MinSelf(&left, indexs[j].front());
MaxSelf(&r, indexs[j].back());
}
}
if (-1 == r)
{
continue;
}
rl.emplace_back(r, left);
}
sort(rl.begin(), rl.end());
int end = -1;
vector<string> vAns;
for (const auto& [r, left] : rl)
{
if (left > end)
{
vAns.emplace_back(s.substr(left, r - left + 1));
end = r;
}
}
return vAns;
}
};
测试用例
template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s;
{
Solution sln;
s = "cabcccbaa";
auto res = sln.maxNumOfSubstrings(s);
Assert({ "cabcccbaa" }, res);
}
{
Solution sln;
s = "ababa";
auto res = sln.maxNumOfSubstrings(s);
Assert({ "ababa" }, res);
}
{
Solution sln;
s = "adefaddaccc";
auto res = sln.maxNumOfSubstrings(s);
Assert({ "e","f","ccc" }, res);
}
{
Solution sln;
s = "abbaccd";
auto res = sln.maxNumOfSubstrings(s);
Assert({ "bb","cc","d" }, res);
}
}
2023年5月
class Solution {
public:
vector maxNumOfSubstrings(string s) {
vector<vector> vIndexs(26);
int index = 0;
for (const char&ch : s)
{
vIndexs[ch - ‘a’].emplace_back(index++);
}
vector<std::pair<int, int>> vEndLen;
m_vNeib.resize(26);
for (int i = 0; i < 26; i++)
{
const auto& v = vIndexs[i];
if (v.empty())
{
continue;
}
int begin = v.front();
int end = v.back();
Do(begin, end, vIndexs);
vEndLen.emplace_back(end, end-begin + 1);
}
std::sort(vEndLen.begin(), vEndLen.end());
int iEnd = -1;
vector vRet;
for (int i = 0; i < vEndLen.size(); i++)
{
const int iBegin = vEndLen[i].first - vEndLen[i].second + 1;
if (iBegin > iEnd)
{
iEnd = vEndLen[i].first;
vRet.emplace_back(s.substr(iBegin, vEndLen[i].second));
}
}
return vRet;
}
void Do(int& begin, int& end, const vector<vector>& vIndexs)
{
for (int i = 0; i < 26; i++)
{
const auto& v = vIndexs[i];
const int iNum = std::upper_bound(v.begin(), v.end(), end) - std::lower_bound(v.begin(), v.end(), begin);
if (0 == iNum)
{
continue;
}
if ((v.front() < begin) || (v.back() > end))
{
begin = min(begin, v.front());
end = max(end, v.back());
Do(begin, end, vIndexs);
break;
}
}
}
vector<vector> m_vNeib;
};
2023年9月
class Solution {
public:
vector maxNumOfSubstrings(string s) {
vector<vector> vIndexs(26);
for (int i = 0; i < s.length(); i++)
{
const int index = s[i] - ‘a’;
vIndexs[index].emplace_back(i);
}
for (int i = 0; i < 26; i++)
{
if (vIndexs[i].empty())
{
continue;
}
DoRightLeft(vIndexs[i].front(), vIndexs[i].back(), vIndexs);
}
sort(m_vRightLeft.begin(), m_vRightLeft.end());
int iPreEnd = -1;
vector vRet;
for (const auto& [r, left] : m_vRightLeft)
{
const int len = r - left + 1;
if (left > iPreEnd)
{
vRet.emplace_back(s.substr(left, len));
iPreEnd = r;
}
}
return vRet;
}
void DoRightLeft(int left, int r, const vector<vector>& vIndexs)
{
bool bAdd = false;
for (int i = 0; i < 26; i++)
{
const auto& v = vIndexs[i];
const int iNum = std::upper_bound(v.begin(), v.end(), r) - std::lower_bound(v.begin(), v.end(), left);
if (0 == iNum)
{
continue;
}
if ((v.front() < left) || (v.back() > r))
{
bAdd = true;
left = min(left, v.front());
r = max(r, v.back());
DoRightLeft(left, r, vIndexs);
break;
}
}
if (bAdd)
{
return;
}
m_vRightLeft.emplace_back(r, left);
}
vector<pair<int,int>> m_vRightLeft;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
