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来自leetlet来自leetlet来自leeteet来自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^4s由小写英文字母组成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 类似只不过我们需要多加几个判断在 stack 栈顶是 letter 的情况不能随意 pop这是因为 pop 可能导致永远无法满足 repetition 个 letter。最后不能直接取 stack 前 remain 个。因为可能导致永远无法满足 repetition 个 letter因此需要记录一下剔除超过 remain 部分元素后我们剔除了多少 letter假设为 m 个之后把末尾的 m 个非 letter 替换为 letter 以满足 repetition 的要求。经过上面的操作我们能保证 stack 是满足 repetition 个 letter 情况下的最小的字典序。为什么不能直接套用 402 模板402 的写法是维护一个单调递增栈允许删除 k 个字符能删就删遍历完后再从栈顶补删到只剩 k 个。它的唯一约束是最终长度 k。2030 多了一条硬性约束结果中letter必须至少出现repetition次。这带来两个连锁问题弹出 letter 需要谨慎如果栈顶恰好是letter直接把它 pop 掉虽然能换来更小字典序但可能把凑齐 repetition 个 letter的希望一并删掉。所以必须用前后缀计数判断删掉这个 letter 之后剩余候选里还能不能凑够 repetition 个。末尾截断可能破坏约束处理完所有字符后栈长度可能超过 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哪怕它使字典序变大。算法细节与完整代码总体流程初始化单调栈stack令remain k最终需要保留的长度同时把k重新赋值为len(s) - k最多允许删除的字符数。从左到右遍历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压入栈。末尾截断并记录缺口while len(stack) remain从栈顶 pop若被 pop 的是 letter 则pre_letters - 1。末尾替换补齐配额从栈底向栈顶扫描前remain个位置即range(remain-1, -1, -1)只要pre_letters repetition且stack[i] ! letter就把该位置改成letter并pre_letters 1。返回.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 计数因此栈内已选 letterpre_letters 未来可选 letterpos_letters就是全串剩余的 letter 总量上界pop 掉一个栈内 letter 后可用的 letter 总量变为pre_letters pos_letters - 1只要这个值还大于等于repetition就存在后面补齐的可行方案pop 不会导致死局。这个判据本质是贪心可行性的前瞻检查它把不能随意 pop从直觉落实成了可编码的条件。关键点三末尾替换为什么不会破坏字典序最小性截断后栈内前remain个字符已经是在配额满足前提下字典序最小的序列。若配额不足必须把某些非 letter 提升为 letter。逆序扫描保证替换从最靠后的位置开始——越靠后的字符对字典序影响越小。这样得到的序列是在所有可行解中字典序最小的那个且由于替换只会让字符变大逆序选择将变大的影响降到最低。同类问题的对比与迁移题目约束单调栈要点402. 移掉 K 位数字只要求长度纯单调栈删除额度为 k删满为止316. 去除重复字母每个字符保留一次单调栈 剩余计数剪枝2030. 含特定字母的最小子序列长度 k letter 至少 repetition 次单调栈 前后缀 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考