What pattern does this problem use?

This problem is based on stack-based state management and monotonic stack logic to enforce lexicographical order and repetition constraints.

Can the stack approach handle large strings efficiently?

Yes, the algorithm processes each character at most twice, resulting in O(n) time complexity even for strings up to length 5*10^4.

How do I ensure the target letter appears at least repetition times?

Track remaining occurrences of the target letter while iterating, and only pop or push characters if doing so preserves enough letters to meet the repetition requirement.

Is it necessary to pop characters that are not the target letter?

Yes, you may pop non-target letters if the current character is smaller and popping won't violate length or repetition constraints to achieve the smallest subsequence.

Does this method always produce the lexicographically smallest subsequence?

Yes, by greedily maintaining a monotonic stack and considering remaining letters, the stack ensures the final subsequence is the smallest possible.

#2030

Hard

auto_awesome栈·状态

LeetCode 题解工作台

含特定字母的最小子序列

给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。返回 s 中长度为 k 且字典序最小的子序列，该子序列同时应满足字母 letter 出现至少 repetition 次。生成的测试用例满足 letter 在 s 中出现至少 repetit…

字符串栈贪心单调栈

题目描述

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

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(k) for the stack used to store the subsequence.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to enforce letter repetition constraints while maintaining lexicographic order?
question_mark
Are you tracking the remaining letters correctly to decide when to pop from the stack?
question_mark
Can you justify why a monotonic stack guarantees the smallest subsequence in this problem?

warning

常见陷阱

外企场景

error
Forgetting to ensure that popping a character does not reduce the available target letters below repetition.
error
Not considering the total remaining letters when deciding to push a character.
error
Trimming the stack incorrectly at the end, leading to length or repetition violations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the lexicographically largest k-length subsequence with a minimum letter occurrence.
arrow_right_alt
Handle multiple letters with individual repetition constraints using a similar stack strategy.
arrow_right_alt
Extend to k-length subsequences where the target letter must appear exactly repetition times instead of at least.

help

常见问题

外企场景

继续练习

#1081 不同字符的最小子序列 #1996 游戏中弱角色的数量 #1963 使字符串平衡的最小交换次数