LeetCode 2030 含特定字母的最小子序列：单调栈 + 前缀计数约束的解法精讲

LeetCode 2030 含特定字母的最小子序列：单调栈 + 前缀计数约束的解法精讲

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文围绕 leetcode 题解仓库 problems/2030.smallest-k-length-subsequence-with-occurrences-of-a-letter.md 展开，深入拆解 LeetCode 2030（含特定字母的最小子序列）这道「单调栈 + 计数约束」的进阶题。它是在经典单调栈题目 402（移掉 K 位数字）基础上引入letter出现次数下限repetition的变体：既要保证结果长度为 k、字典序最小，又必须满足特定字母至少出现 repetition 次。读完本文你将掌握：单调栈如何解决"删除若干字符求最小字典序"这一类问题，以及当引入硬性字符计数约束时，为什么不能直接套用 402 的模板，还需要前缀/后缀计数剪枝与末尾替换两步补救。

题目背景与完整描述

问题定义

题目地址：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 * 10^4
• s由小写英文字母组成
• letter是一个小写英文字母，在s中至少出现repetition次

数据规模达到 5 万级别，说明必须设计 O(n) 或 O(n log n) 级别的算法，O(n²) 的暴力枚举子序列是不可行的——这正是单调栈方案得以成立的前提。

前置知识：单调栈为何适合"删除问题"

本仓库的 thinkings/monotone-stack.md 对单调栈有完整梳理：单调栈是一种"受限再受限"的栈，要求栈内元素始终保持单调递增或单调递减。它的经典适用场景是求解下一个大于 xxx或下一个小于 xxx的位置，其核心机制是：

如果压栈之后仍然可以保持单调性，那么直接压；否则先弹出栈顶元素，直到压入之后可以保持单调性。

被弹出元素的规律可以概括为——被弹出的元素都是大于（或小于）当前元素的，且由于栈本身保持单调，当前元素就是它在右侧遇到的第一个更小（或更大）元素。

而"删除若干字符、求最小字典序"这一类题，恰好可以转化为单调栈问题：为了字典序最小，我们希望越靠前的字符尽可能小。当新字符比栈顶字符更小时，把栈顶字符删掉（pop），让更小的字符提前，就能获得更优的字典序。这就是 402「移掉 K 位数字」的核心思路。

本仓库 thinkings/monotone-stack.md 中给出的通用伪代码模板如下，2030 题正是它的一个受限变体：

class Solution: def monostoneStack(self, arr: List[int]) -> List[int]: stack = [] ans = 定义一个长度和 arr 一样长的数组，并初始化为 -1 循环 i in arr: while stack and arr[i] > arr[栈顶元素]: peek = 弹出栈顶元素 ans[peek] = i - peek stack.append(i) return ans

标准单调栈模板的时间复杂度为 O(n)：每个元素最多入栈、出栈各一次；空间复杂度为 O(n)：栈的长度最大与数组长度一致（见 thinkings/monotone-stack.md 中的复杂度分析）。2030 的解法同样继承这一复杂度特性。

思路演进：从 402 到 2030 的两处关键升级

原题解明确指出：这道题实际上就是 402 号题目的进阶——在"删除字符求最小字典序"的基础上，我们需要多考虑repetition个letter的约束。原文档思路部分的核心原文如下：

和 402 类似，只不过我们需要多加几个判断：

1. 在 stack 栈顶是 letter 的情况不能随意 pop，这是因为 pop 可能导致永远无法满足 repetition 个 letter。
2. 最后不能直接取 stack 前 remain 个。因为可能导致永远无法满足 repetition 个 letter，因此需要记录一下剔除超过 remain 部分元素后，我们剔除了多少 letter（假设为 m 个），之后把末尾的 m 个非 letter 替换为 letter 以满足 repetition 的要求。

经过上面的操作，我们能保证 stack 是满足 repetition 个 letter 情况下的最小的字典序。

为什么不能直接套用 402 模板

402 的写法是：维护一个单调递增栈，允许删除 k 个字符，能删就删；遍历完后再从栈顶补删到只剩 k 个。它的唯一约束是"最终长度 = k"。

2030 多了一条硬性约束：结果中letter必须至少出现repetition次。这带来两个连锁问题：

1. 弹出 letter 需要谨慎：如果栈顶恰好是letter，直接把它 pop 掉虽然能换来更小字典序，但可能把"凑齐 repetition 个 letter"的希望一并删掉。所以必须用前后缀计数判断"删掉这个 letter 之后，剩余候选里还能不能凑够 repetition 个"。
2. 末尾截断可能破坏约束：处理完所有字符后栈长度可能超过 k，需要从栈顶弹出多余元素。如果弹出的恰好是 letter，同样可能把 letter 的数量削减到 repetition 以下；而如果弹出的是非 letter，又可能把本可以替换为 letter 的"弹性空间"挤掉。因此不能简单截断，必须先算出截断后 letter 的缺口，再把末尾足够数量的非 letter 改写成 letter。

核心状态：前缀计数 + 后缀计数

代码中用两个计数器贯穿全过程：

• pre_letters：当前已经进入栈（已选中）的 letter 数量，即前缀方向的计数；
• pos_letters：当前尚未处理的后续字符中 letter 的数量，即后缀方向的计数，初始为s.count(letter)。

二者之和pre_letters + pos_letters代表"当前栈内 letter + 未来还能拿到的 letter"，这是判断"能否安全 pop 掉一个栈内 letter"的唯一依据：如果删掉一个 letter 后pre_letters + pos_letters - 1仍然大于等于repetition，说明后面还能补足配额，可以放心 pop；否则必须保留这个 letter，哪怕它使字典序变大。

算法细节与完整代码

总体流程

1. 初始化单调栈stack，令remain = k（最终需要保留的长度），同时把k重新赋值为len(s) - k（最多允许删除的字符数）。
2. 从左到右遍历s：
   • 若stack非空、stack[-1] > a且还有删除额度（k > 0），尝试 pop：
     • 若栈顶是letter，先检查repetition > pre_letters + pos_letters - 1，成立则 break（不能删，否则配额不足）；否则pre_letters -= 1。
     • 执行stack.pop()，k -= 1。
   • 若当前字符a == letter，同步更新pre_letters += 1、pos_letters -= 1。
   • 无论如何都要把a压入栈。
3. 末尾截断并记录缺口：while len(stack) > remain，从栈顶 pop，若被 pop 的是 letter 则pre_letters -= 1。
4. 末尾替换补齐配额：从栈底向栈顶扫描前remain个位置（即range(remain-1, -1, -1)），只要pre_letters < repetition且stack[i] != letter，就把该位置改成letter并pre_letters += 1。
5. 返回''.join(stack)。

Python3 参考实现

原文档 problems/2030.smallest-k-length-subsequence-with-occurrences-of-a-letter.md 给出的完整实现如下：

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 以满足 repetition 的要求 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)

关键代码逐段精讲

第 2 行：删除额度的换算。目标长度是remain = k，因此最多可以删除len(s) - k个字符。把k重新赋值为删除额度后，单调栈循环中的while k and ...就天然限制了总删除次数，避免最后结果长度小于 k。

第 4~10 行：带配额检查的单调栈维护。while k and stack and stack[-1] > a是 402 的标准骨架：只要栈顶字典序更大且还有删除额度，就弹出。真正新增的是第 7 行——当栈顶恰好是letter时，先算一笔账：pre_letters + pos_letters - 1表示"删掉这个 letter 后，栈内剩余 letter 加上未来所有 letter 的总数"。若它已经小于repetition，说明这个 letter 是"保底配额"，绝不能删，直接break；否则可以安全删除，并同步pre_letters -= 1。

第 11~13 行：状态同步。每个字符无论是否触发 pop 都要入栈。若它是letter，进入栈意味着pre_letters + 1，同时它在后缀中的份额减一（pos_letters -= 1），保证后续判断始终基于"当前真实剩余的未处理字符"。

第 15~18 行：末尾截断。遍历结束后栈长度可能仍大于remain，需要从栈顶 pop 掉多余元素。这一阶段同样要维护pre_letters，因为后面第 20~22 行的替换逻辑依赖它的最新值。

第 19~22 行：末尾替换补齐配额。这是整个算法最精妙的一步。设截断后实际拥有的 letter 数为pre_letters，它与repetition的差就是缺口。为了保持字典序最小，替换应尽量发生在靠后的位置（对字典序影响最小），因此从remain-1向 0 逆序扫描：遇到非 letter 的位置，只要还有缺口就把它改写为letter。由于题目保证s中 letter 总数不少于repetition，缺口一定能在栈内被填满，不会出现无解。

复杂度分析

令 n 为字符串长度：

• 时间复杂度：O(n)。每个字符至多入栈一次、出栈一次；末尾的截断与替换循环各至多 O(n)。整体线性。
• 空间复杂度：O(n)。单调栈最大长度为 n。

三个关键点的工程化解读

关键点一：先剥离约束，它就是一个典型的单调栈题

原题解"关键点"部分明确指出：先不考虑 repetition，这就是一个典型的单调栈题目。这也是拆解复杂题目的通用方法论——先解决无约束版本（402），再为新增约束增量修补。实际编码中，也可以先写出"删除 k 个字符求最小字典序"的纯单调栈版本，跑通后再叠加pre_letters/pos_letters计数与末尾替换，降低出错概率。

关键点二：pre_letters + pos_letters - 1判据为什么"重要"

原代码中该行被注释为"# 重要"。它的正确性建立在两个事实之上：

• pos_letters是尚未遍历的字符中的 letter 计数，因此"栈内已选 letter（pre_letters）+ 未来可选 letter（pos_letters）"就是全串剩余的 letter 总量上界；
• pop 掉一个栈内 letter 后，可用的 letter 总量变为pre_letters + pos_letters - 1，只要这个值还大于等于repetition，就存在"后面补齐"的可行方案，pop 不会导致死局。

这个判据本质是贪心可行性的前瞻检查，它把"不能随意 pop"从直觉落实成了可编码的条件。

关键点三：末尾替换为什么不会破坏字典序最小性

截断后栈内前remain个字符已经是在"配额满足"前提下字典序最小的序列。若配额不足，必须把某些非 letter 提升为 letter。逆序扫描保证替换从最靠后的位置开始——越靠后的字符对字典序影响越小。这样得到的序列是在所有可行解中字典序最小的那个，且由于替换只会让字符变大，逆序选择将"变大"的影响降到最低。

同类问题的对比与迁移

从上面的对比可以看出 2030 的独特之处：它同时存在"长度上限"与"特定字符数量下限"两个相互制约的条件。长度上限由删除额度k控制，字符下限由pre_letters/pos_letters计数控制，而末尾替换则是在两者冲突时（截断后配额不足）进行的最终兜底。理解这三者的配合，也就掌握了这类"带配额单调栈"问题的通用解法骨架。

总结

LeetCode 2030 是一道非常典型的"经典模板 + 新增约束"进阶题：

• 模板层：沿用 402「移掉 K 位数字」的单调递增栈，删除额度换算为len(s) - k；
• 约束层：用pre_letters（前缀已选 letter 数）与pos_letters（后缀剩余 letter 数）维护配额，pop letter 前必须通过repetition > pre_letters + pos_letters - 1的可行性检查；
• 兜底层：末尾截断后若配额不足，逆序把靠后的非 letter 改写为 letter，既满足repetition又保持字典序最小。

整体时间复杂度 O(n)、空间复杂度 O(n)，完全适配 5 × 10⁴ 的数据规模。建议结合 thinkings/monotone-stack.md 中的单调栈原理与通用模板，先独立实现一遍 402，再在此基础上叠加 2030 的计数约束，就能彻底掌握"删除求最小字典序 + 硬性字符配额"这一大类题目的解法。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode