作者推荐
本文涉及的基础知识点
LeetCode3003 执行操作后的最大分割数量
给你一个下标从 0 开始的字符串 s 和一个整数 k。
你需要执行以下分割操作，直到字符串 s 变为 空：
选择 s 的最长前缀，该前缀最多包含 k 个 不同 字符。
删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。
执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。
在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。
示例 1：
输入：s = “accca”, k = 2
输出：3
解释：在此示例中，为了最大化得到的分割数量，可以将 s[2] 改为 ‘b’。
s 变为 “acbca”。
按照以下方式执行操作，直到 s 变为空：
- 选择最长且至多包含 2 个不同字符的前缀，“acbca”。
- 删除该前缀，s 变为 “bca”。现在分割数量为 1。
- 选择最长且至多包含 2 个不同字符的前缀，“bca”。
- 删除该前缀，s 变为 “a”。现在分割数量为 2。
- 选择最长且至多包含 2 个不同字符的前缀，“a”。
- 删除该前缀，s 变为空。现在分割数量为 3。
因此，答案是 3。
可以证明，分割数量不可能超过 3。
示例 2：
输入：s = “aabaab”, k = 3
输出：1
解释：在此示例中，为了最大化得到的分割数量，可以保持 s 不变。
按照以下方式执行操作，直到 s 变为空： - 选择最长且至多包含 3 个不同字符的前缀，“aabaab”。
- 删除该前缀，s 变为空。现在分割数量为 1。
因此，答案是 1。
可以证明，分割数量不可能超过 1。
示例 3：
输入：s = “xxyz”, k = 1
输出：4
解释：在此示例中，为了最大化得到的分割数量，可以将 s[1] 改为 ‘a’。
s 变为 “xayz”。
按照以下方式执行操作，直到 s 变为空： - 选择最长且至多包含 1 个不同字符的前缀，“xayz”。
- 删除该前缀，s 变为 “ayz”。现在分割数量为 1。
- 选择最长且至多包含 1 个不同字符的前缀，“ayz”。
- 删除该前缀，s 变为 “yz”，现在分割数量为 2。
- 选择最长且至多包含 1 个不同字符的前缀，“yz”。
- 删除该前缀，s 变为 “z”。现在分割数量为 3。
- 选择最且至多包含 1 个不同字符的前缀，“z”。
- 删除该前缀，s 变为空。现在分割数量为 4。
因此，答案是 4。
可以证明，分割数量不可能超过 4。
参数范围：
1 <= s.length <= 104
s 只包含小写英文字母。
1 <= k <= 26
分析
变量解析
| dpNotChange | dpNotChange[i]表示子串s[i,m_c)的最大分割数 |
| vSplit | vSplit[inx][i]=j表示：将s[i]修改成’a’+inx，其它字符不变的情况下，s[i，m_c)的最长前缀是s[i,j) |
不修改任何字符的情况下，s拆分成m个子串，分别为[li1,ri1),[li2,ri2)… [lim,rim)。
显然 li1等于0,rim等于m_c， ri1等于li2…
分以下情况:
- 一，没有改变任何字符。
- 二，改变某个字后,[lix,rix)发生改变，变成[lix,nix)，只需要考虑nix < rix，原因见下文证明一。
情况二：
分两层循环：
- 第一层循环：枚举不修改字符的子串。
- 第二层循环：枚举nix。
两层循环的时间复杂度为：O(s.length)。
枚举nix的时候，分两种情况：
一，s[nix]没有改变，s[nix,m_c)的最大分割数就是dpNotChange[rix]。前提条件是：
- k<26 否则无论变成k+1。
- 包括nix，目前已经有k个不同字符
- [lix,nix]至少有k+1个字符，由于其只有k个不同字符，所以至少有两个字符相同，去掉nix，[lix,nix)至少还有一个相同字符，将其改成k个字符以外的字符。只能证明[lix,rix]有k+1个字符，不能证明是第一个rix。假定第一个rix是rix1，rix会被rix1淘汰，所以不会造成错误。原因见证明一。
二，枚举s[nix]改成’a’到’z’。通过vSplit查询第一个前缀。
通过滑动窗口计算vSplit[inx][i-1]
s[i,rightk] 共有k个字符，rightk取最小值；是s[i,rightk1]共有k+1个字符，rightk1取最小值。如果没有足够的字符取m_c。
countk 记录了这k个字符，countk1记录了k+1个字符。
| countk 包括inx+‘a’ | countk1的数量为k+1 | 结果为：rightk1 |
| countk 包括inx+‘a’ | countk1的数量不够k+1 | 结果为：m_c |
| countk 不包括inx+‘a’ | countk的数量为k | 结果为：rightk |
| countk 不包括inx+‘a’ | countk的数量不够k | 结果为：m_c |
证明一 i1<=12则dpNotChange[i1] >= dpNotChange[i2]
特殊情况一：如果s[i1,m_c)和s[i2,m_c) 都不到k+1个字符。则两者都为1。
特殊情况二：s[i2,m_c) 不到k+1个字符，s[i1,m_c)有k+1个字符，则前者为1，后者超过1。
s[i1,m_c) 不到k+1个字符，s[i2,m_c)有k+1个字符，这种i情况不存在。
如果两者都有k+1字符
则s[i2,m_c)可以拆分s[i2,i4)和s[i4,m_c)
s[i1,m_c)可以拆分成s[i1,i3)和s[i3,m_c)
则i3<=i4，i1变i3变大;i2变i4，每次迭代i1和i2都变大，若干次后一定会变成特殊情况一或特殊情况二。
假定i3>i4
s[i2,i4]刚好k+1个字符，那么s[i1,i2)+s[i2,i4]+s(i4+i3)的字符数大于等于k+1,这三个子串加在一起就是s[i1,i3)，与s[i1,i3)只有k个字符矛盾。
代码
核心代码
template<class KEY>
class CKeyCount
{
public:
void Add(const KEY& key, int iCount)
{
Cnt[key] += iCount;
if (0 == Cnt[key])
{
Cnt.erase(key);
}
}
std::unordered_map<KEY, int> Cnt;
};
class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
m_c = s.length();
vSplit[inx][i]=j表示：将s[i]修改成'a'+inx，其它字符不变的情况下，s[i，m_c)的最长前缀是s[i,j)
vector<vector<int>> vSplit(26,vector<int>(m_c, m_c));
for (int inx = 0; inx < 26; inx++)
{
CKeyCount<char> countk1,countk;
//s[i,rightk] 共有k个字符，rightk取最小值；是s[i,rightk1]共有k+1个字符，rightk取最小值。如果没有足够的字符取m_c
for (int i =1, rightk1 =i-1,rightk=i-1; i < m_c;i++ )
{ //s(left,right]和inx+'a' 刚好k+1
while ((rightk +1 < m_c)&&(countk.Cnt.size() < k ))
{
countk.Add(s[++rightk],1);
}
while ((rightk1 + 1 < m_c) && (countk1.Cnt.size() <= k))
{
countk1.Add(s[++rightk1], 1);
}
if (countk.Cnt.count('a' + inx))
{
vSplit[inx][i - 1] = (k + 1 == countk1.Cnt.size()) ? rightk1 : m_c;
}
else
{
vSplit[inx][i - 1] = (k == countk.Cnt.size()) ? rightk : m_c;
}
countk.Add(s[i], -1);
countk1.Add(s[i], -1);
}
}
vector<int> dpNotChange(m_c + 1, 0);//dp1[i]=x表示 ，在不修改的情况下 s[i,m_c)最多可以分割x次
for (int i = m_c - 1; i >= 0; i--)
{
int inx = vSplit[s[i]-'a'][i];
dpNotChange[i] = dpNotChange[inx] + 1;
}
int iRet = dpNotChange.front();
int iPreNum = 0;
for (int i = 0; i < m_c; i = vSplit[s[i]-'a'][i])
{
iPreNum++;
set<char> setHas;
for (int j = i; j < vSplit[s[i] - 'a'][i]; j++)
{
if (setHas.size()==k)
{
for (char ch = 'a'; ch <= 'z'; ch++)
{//修改了j，且s[j]是新的子串的开始
if (!setHas.count(ch))
{
const int inx = vSplit[ch - 'a'][j];
iRet = max(iRet, iPreNum + 1 + dpNotChange[inx]);
}
}
}
setHas.emplace(s[j]);
if ((setHas.size() == k)&&(k< 26)&&(j-i+1 > k ))
{
iRet = max(iRet, iPreNum + dpNotChange[j]);
}
}
}
return iRet;
}
int m_c;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
测试用例
template<class T>
void Assert(const T& t1, const T& 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;
int k;
{
Solution sln;
s = "baac", k = 3;
auto res = sln.maxPartitionsAfterOperations(s, k);
Assert(2, res);
}
{
Solution sln;
s = "accca", k = 2;
auto res = sln.maxPartitionsAfterOperations(s, k);
Assert(3, res);
}
{
Solution sln;
s = "aabaab", k = 3;
auto res = sln.maxPartitionsAfterOperations(s, k);
Assert(1, res);
}
{
Solution sln;
s = "xxyz", k = 1;
auto res = sln.maxPartitionsAfterOperations(s, k);
Assert(4, res);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
两个错误代码
都没有考虑s[nix]会修改。
class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
m_c = s.length();
vector
{
CKeyCount count;
for (int i = 0, right = 0; i < m_c; i++)
{
while ((right < m_c) && (count.Cnt.size() <= k))
{
count.Add(s[right++], 1);
}
vSplit[0][i] = right;
count.Add(s[i], -1);
}
}
{
CKeyCount count;
for (int i = 0, right = 0; i < m_c; i++)
{
while ((right < m_c) && (count.Cnt.size() < k))
{
if ((count.Cnt.size() == k) && (right - i > k))
{
break;
}
count.Add(s[right++], 1);
}
vSplit[1][i] = right;
count.Add(s[i], -1);
}
}
vector
dp[0][0] = 0;
dp[1][1] = -m_c;
for (int i = 0; i < m_c; i++)
{
//没改字符=>没改字符
dp[0][vSplit[0][i]] = max(dp[0][vSplit[0][i]], dp[0][i] + 1);
//没改字符=>改字符
dp[1][vSplit[1][i]] = max(dp[1][vSplit[1][i]], dp[0][i] + 1);
//改字符=>改字符
dp[1][vSplit[0][i]] = max(dp[1][vSplit[0][i]], dp[1][i] + 1);
}
return max(dp[0].back(), dp[1].back());
}
int m_c;
};
class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
m_c = s.length();
vector vSplit(m_c, m_c);//vSplit[i]=j表示，在不修改的情况s[i，m_c)的最长前缀是s[i,j)
CKeyCount count;
for (int i = 0, right = 0; i < m_c; i++)
{
while ((right < m_c) && (count.Cnt.size() <= k))
{
count.Add(s[right++], 1);
}
vSplit[i] = right;
count.Add(s[i], -1);
}
vector dpNotChange(m_c+1, 0);//dp1[i]=x表示 ，在不修改的情况下 s[i,m_c)最多可以分割x次
for (int i = m_c - 1; i >= 0; i--)
{
dpNotChange[i] = max(dpNotChange[i], dpNotChange[vSplit[i]] + 1);
}
int iRet = dpNotChange.front();
int iPreNum = 0;
for (int i = 0; i < m_c; i = vSplit[i])
{
iPreNum++;
CKeyCount cnt;
for (int j = i; j < vSplit[i]; j++)
{
cnt.Add(s[j], 1);
if ((cnt.Cnt.size() == k) && (j - i + 1 > k))
{
iRet = max(iRet, iPreNum + dpNotChange[j]);
}
}
}
return iRet;
}
int m_c;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。
QQ群名片
评论记录：
回复评论：