作者推荐
本文涉及的基础知识点
题目
给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。
返回 s 中长度为 k 且 字典序最小 的子序列，该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现 至少 repetition 次。
子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。
字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。
示例 1：
输入：s = “leet”, k = 3, letter = “e”, repetition = 1
输出：“eet”
解释：存在 4 个长度为 3 ，且满足字母 ‘e’ 出现至少 1 次的子序列：
- “lee”（“leet”）
- “let”（“leet”）
- “let”（“leet”）
- “eet”（“leet”）
其中字典序最小的子序列是 “eet” 。
示例 2：
输入：s = “leetcode”, k = 4, letter = “e”, repetition = 2
输出：“ecde”
解释：“ecde” 是长度为 4 且满足字母 “e” 出现至少 2 次的字典序最小的子序列。
示例 3：
输入：s = “bb”, k = 2, letter = “b”, repetition = 2
输出：“bb”
解释：“bb” 是唯一一个长度为 2 且满足字母 “b” 出现至少 2 次的子序列。
参数范围：
1 <= repetition <= k <= s.length <= 5 * 104
s 由小写英文字母组成
letter 是一个小写英文字母，在 s 中至少出现 repetition 次
单调栈
最简单的情况：不限制长度和重复字符
从左到右将s[i]放到栈中，放入之前向将栈中大于s[i]的出栈。下面来证明：
假定s的最小子系列的为依次为：{i1,i2,i3…}。
规则一：i1之前没有数小于等于它。否则将此数的放在最前会变得最小。
规则二：i1之后没有数小于它，否则替换i1会变得更小。
规则三：i1和i2之间没有数小于等于i2。
规则四：i2之后没有数小于它，否则替换i2会变得更小。
…
栈底到栈顶就是最小子系列。
i1在栈底，说明它前面的数都大于它，所以出栈了。
i1没有出栈，说明i1之后没有数比它小，否则i1出栈了。
i2之前，i1之后没有数据，说明两者之间没有数小于等于i2，否则不会出栈。
i2没有出栈说明之后没有数据小于它，否则出栈了。
…
大数出栈后，变成前面的数小，后面的数大。也就是递增的单调栈。
注意: {1,1,1} 前面增加1，变成{1,1,1,1} 有些规则可能变小，有些规则可能变大。
限制长度k
限制了长度，也就限制了出栈次数。前面的数变小比后面的数变小更小，所以把出栈的机会留给前面。
出栈的时候增加判断：如果出栈后，使得长度一定少于k则不出栈。
入栈的时候增加判断：如果长度已经为k，则不入栈。
必须特定个特定字母
如果出栈会造成特定字母不足则不出栈。
入栈时增加处理：如果长度为k，但当前是特定字母，不入栈则特定字母不足，出栈栈顶所有特定字母，直到非特定字母。出栈它，把出栈的特定字母和当前字母入栈。这个操作在超时的边缘。
代码
核心代码
class Solution {
public:
string smallestSubsequence(const string s, const int k, const char letter, const int repetition) {
int iCanOutCount = std::count(s.begin(), s.end(), letter) - repetition;//可以不使用letter的数量
vector<char> sta;
for (int i = 0; i < s.length(); i++)
{
const auto& ch = s[i];
auto NeedPop = [&]()
{
if (sta.empty() || (sta.size() + s.length() - i <= k) || (sta.back() <= ch))
{
return false;
}
if ((sta.back() == letter) && (iCanOutCount <= 0))
{
return false;
}
return true;
};
while (NeedPop())
{
iCanOutCount -= (sta.back() == letter);
sta.pop_back();
}
if (sta.size() < k)
{
sta.emplace_back(ch);
}
else if ((letter == ch)&&( iCanOutCount <= 0 ))
{
int iCnt = 1;
while (sta.size()+ iCnt > k )
{
if (letter == sta.back())
{
iCnt++;
}
sta.pop_back();
}
while (iCnt--)
{
sta.emplace_back(letter);
}
}
else
{
iCanOutCount -= (letter == ch);
}
}
sta.emplace_back(0);
return sta.data();
}
};
- 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
测试用例
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;
char letter;
int repetition;
{
Solution slu;
s = "leet", k = 3, letter = 'e', repetition = 1;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("eet"), res);
}
{
Solution slu;
s = "leetcode", k = 4, letter = 'e', repetition = 2;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("ecde"), res);
}
{
Solution slu;
s = "bb", k = 2, letter ='b', repetition = 2;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("bb"), res);
}
{
Solution slu;
s = "aaabbbcccddd", k = 3, letter = 'b', repetition = 2;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("abb"), res);
}
{
Solution slu;
s = "hjjhhhmhhwhz", k = 6, letter = 'h', repetition = 5;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("hhhhhh"), res);
}
//CConsole::Out(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
- 55
- 56
- 57
- 58
- 59
- 60
- 61
优化
非特定字母最多入栈：k - repetition。注意 ：非特定字母入栈的时候，也要判断栈的长度小于k。
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;
char letter;
int repetition;
{
Solution slu;
s = "leet", k = 3, letter = 'e', repetition = 1;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("eet"), res);
}
{
Solution slu;
s = "leetcode", k = 4, letter = 'e', repetition = 2;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("ecde"), res);
}
{
Solution slu;
s = "bb", k = 2, letter ='b', repetition = 2;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("bb"), res);
}
{
Solution slu;
s = "aaabbbcccddd", k = 3, letter = 'b', repetition = 2;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("abb"), res);
}
{
Solution slu;
s = "hjjhhhmhhwhz", k = 6, letter = 'h', repetition = 5;
auto res = slu.smallestSubsequence(s, k, letter, repetition);
Assert(std::string("hhhhhh"), res);
}
//CConsole::Out(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
- 55
- 56
- 57
- 58
- 59
- 60
- 61
2023年3月旧版
class Solution {
public:
string smallestSubsequence(string s, int k, const char letter, int repetition) {
m_c = s.length();
int iCanNotUseLetterNum = -repetition;//可以不使用letter多少次
int iCanNotUseChar = m_c - k;
vector vAns;
for (const auto& ch : s)
{
if (ch == letter)
{
iCanNotUseLetterNum++;
}
}
for (int i = 0; i < m_c; i++)
{
const auto& ch = s[i];
while (vAns.size() && (ch < vAns.back()) && iCanNotUseChar && ((letter != vAns.back()) || iCanNotUseLetterNum))
{
if (letter == vAns.back())
{
iCanNotUseLetterNum–;
}
iCanNotUseChar–;
vAns.pop_back();
}
vAns.push_back(ch);
}
string strRet;
for (int iIndex = vAns.size() - 1; iIndex >= 0; iIndex–)
{
const char& ch = vAns[iIndex];
if (0 == iCanNotUseChar)
{
strRet += ch;
continue;
}
if (letter == ch )
{
if (iCanNotUseLetterNum)
{
iCanNotUseLetterNum–;
iCanNotUseChar–;
}
else
{
strRet += ch;
}
}
else
{
iCanNotUseChar–;
}
}
vector tmp(strRet.rbegin(), strRet.rend());
tmp.push_back(0);
return tmp.data();
}
int m_c;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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群名片
评论记录：
回复评论：