含特定字母的最小子序列

难度: Hard

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

example-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 * 10⁴
s 由小写英文字母组成
letter 是一个小写英文字母，在 s 中至少出现 repetition 次

Submission

运行时间: 283 ms

内存: 17.1 MB

class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        stack = []
        remove = len(s) - k
        remainder = s.count(letter)
        for c in s:
            while remove and stack and c < stack[-1]:
                if stack[-1] == letter and remainder == repetition:
                    break
                if stack.pop() == letter:
                    remainder -= 1
                remove -= 1
            stack.append(c)
        stack = stack[:k]
        cur = stack.count(letter)
        if cur < repetition:
            for i in range(k -1, -1, -1):
                if cur == repetition:
                    break
                if stack[i] != letter:
                    stack[i] = letter
                    cur += 1
        return "".join(stack)

Explain

该题解采用单调栈的方法来构建字典序最小的子序列。首先，遍历字符串s，利用栈来存储潜在的最小字典序的子序列。在遍历过程中，如果当前字符c小于栈顶字符并且还有足够的空间（可以移除的字符数remains > 0）来满足最终序列长度为k，就尝试将栈顶字符弹出，直到无法弹出（栈空、当前字符不再小于栈顶字符、或者弹出后无法满足letter的repetition要求）。为了确保生成的子序列中letter出现至少repetition次，需要统计letter的总出现次数以及在栈中的数量，确保不会因为弹出操作而使得letter的数量不足。遍历完成后，如果栈中letter的数量不足，从栈尾开始替换非letter字符直到满足条件。最终，截取栈中前k个字符作为结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        stack = [] # 初始化栈
        remove = len(s) - k # 可以移除的字符数
        remainder = s.count(letter) # s中letter的总数量
        for c in s: # 遍历字符串s的每个字符
            while remove and stack and c < stack[-1]: # 栈非空且当前字符小于栈顶字符且还可以移除字符
                if stack[-1] == letter and remainder == repetition: # 栈顶字符为letter且letter数量刚好满足要求时不能移除
                    break
                if stack.pop() == letter: # 弹出字符，如果是letter则更新计数
                    remainder -= 1
                remove -= 1 # 更新可移除字符数量
            stack.append(c) # 将当前字符加入栈
        stack = stack[:k] # 取栈中前k个元素
        cur = stack.count(letter) # 统计栈中letter的数量
        if cur < repetition: # 如果letter数量不足
            for i in range(k -1, -1, -1): # 从后向前遍历栈
                if cur == repetition: # 已满足letter的数量要求
                    break
                if stack[i] != letter: # 替换非letter字符为letter
                    stack[i] = letter
                    cur += 1
        return ''.join(stack) # 将栈转换为字符串并返回

Explore

单调栈的主要目的是维护一个字典序最小的序列。如果直接添加所有字符到栈中，将无法保证最终结果的字典序最小。弹出栈顶字符的操作是为了在遇到一个字典序较小的字符时，移除前面较大的字符，从而使整个栈保持字典序最小。此外，这种操作还有助于调整栈的大小以确保最终的序列长度为k。

算法通过记录`s`中`letter`的总数量以及在栈中的数量来确保`letter`至少出现`repetition`次。在每次弹出栈顶字符时，若栈顶字符是`letter`，会检查剩余的`letter`数量是否还能满足`repetition`的要求。如果弹出当前`letter`后，剩余的`letter`数量加上栈中的`letter`数量小于`repetition`，则停止弹出操作。这确保了即使在尝试获取字典序最小的子序列时，也不会破坏对`letter`数量的要求。

这种操作可能会影响到子序列的字典序最小性。尽管如此，由于替换发生在栈的尾部，并且只在必要时进行（即当`letter`数量不足以满足`repetition`要求时），因此对整体字典序的影响是有限的。实际上，这是一种折衷方案，用来在满足`letter`数量要求的同时尽可能保持子序列的字典序较小。

当输入字符串`s`的长度等于所需子序列长度`k`时，算法简化为必须使用所有字符，因此不需要执行任何字符的移除操作。在这种情况下，只需确保生成的序列中`letter`字符出现至少`repetition`次。如果`letter`数量不足，将按照先前的逻辑替换足够的非`letter`字符以满足条件。