[Leetcode]2030 含特定字母的最小子序列

261周赛补题T4

2030. 含特定字母的最小子序列

给你一个字符串 s ,一个整数 k ,一个字母 letter 以及另一个整数 repetition

返回 s 中长度为 k字典序最小 的子序列,该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letters 中出现 至少 repetition 次。

子序列 是由原字符串删除一些(或不删除)字符且不改变剩余字符顺序得到的剩余字符串。

字符串 a 字典序比字符串 b 小的定义为:在 ab 出现不同字符的第一个位置上,字符串 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:

[Leetcode]2030 含特定字母的最小子序列

输入: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,后子串为s2s1+s[i]+s2肯定大于s1+s[i+1]+s2,如果能去掉的话则优先去掉,不能去掉则保留,这里证明一下为什么去掉靠前的优先去掉靠后的。假设去掉靠前(s[i])的字符ans1s1+s[i+1]+s2,去掉靠后(s[j])的字符ans2s1+s[i]+s[i+1]+s3+s[j+1]+s4,然而因为最后答案字符串长度都为k,则在比较ans1ans2时,在比较s1.size()+1ans1已经小于ans2,后面也没有比较的必要,因此优先删除靠前子串。在删除时如果遇到了letter,则要考虑有没有足够空白来删除,区分一下就能解决。

s1.size()+1ans1已经小于ans2,后面也没有比较的必要,因此优先删除靠前子串。在删除时如果遇到了letter,则要考虑有没有足够空白来删除,区分一下就能解决。

[Leetcode]2030 含特定字母的最小子序列

上一篇:单词按照首字母分类


下一篇:TODO 进行判断字符串是否有效