# 2030. 含特定字母的最小子序列
### 题目地址(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 次
```
### 前置知识
* 单调栈
### 公司
* 暂无
### 思路
之前我写了一篇文章，里面详细介绍了单调栈解决这种删除若干并求最小（或最大）字典序的题目，没有看过的建议先看下那篇文章 [一招吃遍力扣四道题，妈妈再也不用担心我被套路啦～](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:
```python
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-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 45K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2030.smallest-k-length-subsequence-with-occurrences-of-a-letter.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.