261周赛补题T4
2030. 含特定字母的最小子序列
给你一个字符串 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次
class Solution {
public:
string smallestSubsequence(string s, int k, char letter, int repetition) {
string ans = "";
int n = s.size(), d = n - k, dl = 0;
for(auto &e : s){
if(e == letter)dl ++;
}
dl -= repetition;
for(int i = 0; i < n; ++ i){
while(d > 0 && ans.empty() == false && s[i] < ans[ans.size() - 1]){
if(ans[ans.size() - 1] == letter){
if(dl > 0){
ans.pop_back();
dl --;
d --;
}else break;
}else{
ans.pop_back();
d --;
}
}
ans += s[i];
}
int cnt = 0;
for(int i = 0; i < d; ++ i){
if(ans[ans.size() - 1] == letter){
if(dl == 0){
cnt ++;
d ++;
}else{
dl --;
}
}
ans.pop_back();
}
for(int i = 0; i < cnt; ++ i)ans += letter;
return ans;
}
};
算法思路
这题的主要难点是贪心，这题求子序列，则要在原字符串里去掉一些子串，这里的贪心选择是优先去掉靠前的。这里说一下最小字典序子序列，当我们有足够空格去去除字符串的某些字符时，应该优先去掉靠前的，当s[i]>s[i+1]时，如果能去掉s[i]则优先去掉s[i]，假设这两部分的前子串为s1，后子串为s2，s1+s[i]+s2肯定大于s1+s[i+1]+s2，如果能去掉的话则优先去掉，不能去掉则保留，这里证明一下为什么去掉靠前的优先去掉靠后的。假设去掉靠前(s[i])的字符ans1为s1+s[i+1]+s2，去掉靠后(s[j])的字符ans2为s1+s[i]+s[i+1]+s3+s[j+1]+s4，然而因为最后答案字符串长度都为k，则在比较ans1和ans2时，在比较s1.size()+1时ans1已经小于ans2，后面也没有比较的必要，因此优先删除靠前子串。在删除时如果遇到了letter，则要考虑有没有足够空白来删除，区分一下就能解决。
s1.size()+1时ans1已经小于ans2，后面也没有比较的必要，因此优先删除靠前子串。在删除时如果遇到了letter，则要考虑有没有足够空白来删除，区分一下就能解决。