题目
给你一个字符串 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(); } };
测试用例
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); }
优化
非特定字母最多入栈：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); }
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++ 实现。
