列表

详情


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:

example-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 次的子序列。

 

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: string smallestSubsequence(string s, int k, char letter, int repetition) { } };

python3 解法, 执行用时: 1500 ms, 内存消耗: 18.8 MB, 提交时间: 2023-09-06 23:31:04

class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        n = len(s)

        #----后缀,右侧出现指定字母的次数
        suffix_cnt = [0 for _ in range(n)]
        acc = 0
        for i in range(n - 1, -1, -1):
            acc += (s[i] == letter)
            suffix_cnt[i] = acc
        
        stk = []
        x = 0           #letter在res中已经出现的次数
        for i in range(0, n):
            y = x       #因为可能会操作,操作过程中letter在res中出现的次数
            #----弹栈
            while stk != [] and len(stk) + (n - i - 1) >= k and s[i] < stk[-1]:
                if stk[-1] == letter:
                    y -= 1
                if y + suffix_cnt[i] < repetition:
                    break
                #--正式删
                stk.pop(-1)
                x = y

            #----压栈
            if len(stk) < k:
                if s[i] == letter or k - len(stk) > repetition - x:
                    stk.append(s[i])
                    if s[i] == letter:
                        x += 1
        
        return ''.join(stk)

cpp 解法, 执行用时: 120 ms, 内存消耗: 28.3 MB, 提交时间: 2023-09-06 23:30:30

class Solution {
public:
    string smallestSubsequence(string s, int k, char letter, int repetition ) {
        int  n = s.size();
        int cnt = 0;  // 后面还未扫描到的 letter的数量
        for(int i = 0 ; i < n; ++ i)  //统计letter出现的数量
            if(s[i] == letter) cnt++ ; 
        int toErase = n - k;   // 要删去n - k 个元素
        string res;         // 答案
        int p = 0;          // 目前为止letter已扫描了的次数
        for(int i = 0 ;i < n; ++ i)
        {
            while(toErase && res.size() && s[i] < res.back()){  // 删去逆序的字母
                if(res.back() == letter){
                    if(repetition  > p - 1 + cnt)  // 后面的letter 不够凑成repetition 个letter
                        break;
                    p -- ;      // 可以删除
                }
                res.pop_back();
                toErase -- ;  //删去一个
            }
            if(s[i]== letter) p ++ , cnt -- ;  // 前面增加,后面减少
            res += s[i];
        }
        
        while(res.size() > k){      // 是因为逆序字母可能不够的原因 会漏删一些 元素,现在检查补上
            if(res.back() == letter) p -- ;
            res.pop_back();
        }
        for(int i = k - 1;i >= 0; -- i){ // 因为前面的元素可能比letter更小,所以要检查一下补上letter
            if(p < repetition  && res[i] != letter) {//(这是为了保证letter个数足够,但letter不够小,所以得从后往前补,保证最小)
                res[i] = letter;
                ++ p;
            }   
        }
        return res;
    }
};

golang 解法, 执行用时: 40 ms, 内存消耗: 7 MB, 提交时间: 2023-09-06 23:29:52

// 单调队列
func smallestSubsequence(s string, k int, letter byte, repetition int) string {
	ans := []byte{}
	unread := strings.Count(s, string(letter)) // 未遍历到的 letter 个数
	inQ := 0 // 在单调队列中的 letter 个数
	q := []byte{}
	for i, n := 0, len(s); len(ans) < k; i++ {
		// 将 s[i] 插入单调队列
		for i < n && len(q) > 0 && s[i] < q[len(q)-1] {
			if q[len(q)-1] == letter { // 特判队尾是 letter 的情况
				if inQ+unread <= repetition { // 弹出队尾会导致无法凑足 repetition 个 letter,及时退出
					break
				}
				inQ--
			}
			q = q[:len(q)-1]
		}
		if i < n {
			if s[i] == letter {
				unread--
				inQ++
			}
			q = append(q, s[i])
		}

		if i >= n-k {
			// 从队首拿到字典序最小的字符
			if q[0] == letter {
				inQ--
				repetition--
				ans = append(ans, q[0])
			} else if len(ans)+repetition < k { // 还有足够空间可以放 letter
				ans = append(ans, q[0])
			}
			q = q[1:]
		}
	}
	return string(ans)
}

上一题