- [2030. 含特定字母的最小子序列](./problems/2030.smallest-k-length-subsequence-with-occurrences-of-a-letter.md)

- [2030. 含特定字母的最小子序列](./problems/2030.smallest-k-length-subsequence-with-occurrences-of-a-letter.md)

- 单调栈

- 暂无

之前我写了一篇文章，里面详细介绍了单调栈解决这种删除若干并求最小（或最大）字典序的题目，没有看过的建议先看下那篇文章 [一招吃遍力扣四道题，妈妈再也不用担心我被套路啦～](https://lucifer.ren/blog/2021/02/20/%E5%88%A0%E9%99%A4%E9%97%AE%E9%A2%98/)。

这道题实际上就是上文提到的 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

Python3 Code:

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)$

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 45K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。