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

Question

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

前置知识

• 单调栈

思路

之前我写了一篇文章，里面详细介绍了单调栈解决这种删除若干并求最小（或最大）字典序的题目，这道题实际上就是上文提到的 402 号题目的进阶。也就是我们需要多考虑 repetition 个 letter 的情况。

和 402 类似，只不过我们需要多加几个判断：

1. 在 stack 栈顶是 letter 的情况不能随意 pop，这是因为 pop 可能 导致永远无法满足 repetition 个 letter。
2. 最后不能直接取 stack 前 remain 个。因为可能导致永远无法满足 repetition 个 letter，因此需要记录一下剔除超过 remain 部分元素后，我们剔除了多少 letter（假设为 m 个），之后把末尾的 m 个非 letter 替换为 letter 以满足 repetiton 的要求

经过上面的操作，我们能保证 stack 是满足 repetition 个 letter 情况下的最小的字典序。

关键点

• 先不考虑 repetition，这就是一个典型的单调栈题目

代码

• 语言支持：Python3

class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        stack = []
        remain, k = k, len(s) - k
        pre_letters, pos_letters = 0, s.count(letter)
        for a in s:
            while k and stack and stack[-1] > a:
                if stack[-1] == letter:
                    if repetition > pre_letters + pos_letters - 1: break # 重要
                    pre_letters -= 1
                stack.pop()
                k -= 1
            if a == letter:
                pre_letters += 1
                pos_letters -= 1
            stack.append(a)
        # 不能直接取前 remain 个，因为可能不满足 repetition 的要求，因此需要记录一下剔除超过 remain 部分元素后，我们剔除了多少 letter（假设为 m 个），之后把末尾的 m 个非 letter 替换为 letter 以满足  repetiton 的要求
        while len(stack) > remain:
            if stack[-1] == letter:
                pre_letters -= 1
            stack.pop()
        for i in range(remain-1,-1,-1):
            if pre_letters < repetition and stack[i] != letter:
                pre_letters += 1
                stack[i] = letter
        return ''.join(stack)

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$