2030. 含特定字母的最小子序列

题目地址(2030. 含特定字母的最小子序列)

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 类似,只不过我们需要多加几个判断:

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

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

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

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

最后更新于