https://leetcode-cn.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/
给你一个字符串 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 类似，只不过我们需要多加几个判断：
- 在 stack 栈顶是 letter 的情况不能随意 pop，这是因为 pop
可能导致永远无法满足 repetition 个 letter。 - 最后不能直接取 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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 45K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
