class Solution {
public:
string smallestSubsequence(string s, int k, char letter, int repetition) {
}
};
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
次原站题解
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) }