第六章 - 高频考题(困难)
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 次

前置知识

  • 单调栈

公司

  • 暂无

思路

之前我写了一篇文章,里面详细介绍了单调栈解决这种删除若干并求最小(或最大)字典序的题目,没有看过的建议先看下那篇文章 一招吃遍力扣四道题,妈妈再也不用担心我被套路啦~
这道题实际上就是上文提到的 402 号题目的进阶。也就是我们需要多考虑 repetition 个 letter 的情况。
和 402 类似,只不过我们需要多加几个判断:
  1. 1.
    在 stack 栈顶是 letter 的情况不能随意 pop,这是因为 pop 可能 导致永远无法满足 repetition 个 letter
  2. 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)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 45K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。