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

Difficulty

Hard

Tags

单调栈

URL

https://leetcode.cn/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/

Star

给你一个字符串 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 次

法1 单调栈

思路

🧧

402. 移掉 K 位数字的进阶题目。

402 要求删掉 k 个字母，本题有两个要求：

删掉 len(s) - k 个字母

删掉 s.count(letter) - repetition 个字母letter

所以大致思路完全一致：先构造一个递增的序列，然后如果还有没删完的，即还有删除的权力，那就继续倒着删除。

注：本题最后倒着删除利用了一个技巧。详见代码

题解


class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        
        stack = []
        # 最多能删的次数
        remove = len(s) - k
        # 最多能删的 letter 次数
        remove_letter = s.count(letter) - repetition

        for char in s:
            while stack and char < stack[-1] and remove > 0:
                if stack[-1] == letter:
                    if remove_letter <= 0:
                        break
                    remove_letter -= 1

                stack.pop()
                remove -= 1

            stack.append(char)
    

        # 构造出了一个递增的序列
        # 如果还有字母没删完，即长度超过了k, 可以直接抛弃超过k的部分
        stack = stack[:k]

        # 如果抛弃之后，letter的数量不够了，那就倒着填充
        # 因为要的是子序列，倒着填充可以保证 后面抛弃的 letter 和前面的顺序
        temp = stack.count(letter)
        if temp < repetition:
            for i in range(len(stack)-1, -1, -1):
                if stack[i] != letter:
                    stack[i] = letter
                    temp += 1

                if temp == repetition:
                    break
        
        return "".join(stack)

注：单调栈那里也可以写作如下：


while stack and char < stack[-1] and remove > 0 and (stack[-1] != letter or remove_letter > 0):
    if stack[-1] == letter:
        remove_letter -= 1
    remove -= 1
    stack.pop()
                
stack.append(char)