先交代一下背景这道题我是在整理字符串类动态规划题目的时候重新刷到的。Leetcode 1653题名很直白使字符串平衡的最少删除次数。给定一个只包含字符a和b的字符串s每次可以删除任意一个字符问最少删除多少个字符能让剩下的字符串变成“平衡”的。这里的平衡定义非常微妙它不是说a和b的数量一样多也不是什么括号匹配而是剩下的字符串中不能出现ba这个子序列也就是说字符串里一旦出现了b那后面就不能再出现a。直白点讲最终合法的字符串一定是形如若干a后面跟着若干b也就是正则表达式a*b*的结构。这个题非常适合用来练动态规划也能引申出多种解法从二维 DP 到一维滚动数组再到 O(n) 的一次扫描贪心一层层优化下来非常有意思。我刚接触这道题的时候第一反应是暴力枚举删除哪些字符马上意识到不可能字符串长度最高能到十万级别每个字符删或不删就是 2 的 N 次方种方案直接爆炸。后来老老实实从“合法子序列”的角度想才发现这题本质上是在找一个最长的、形状为a*b*的子序列然后用总长度减掉它就是最少删除次数。这篇文章我把整个思考过程、三种主流解法、还有我实际提交时踩过的几个坑都写下来给准备面试或者刷动态规划的朋友做个参考。1. 看懂题目字符串平衡到底在说什么1.1 原题描述与示例回顾先把题目的原始定义摆出来。给定字符串s只含小写字母a和b每次操作可以从s中删除任意一个字符。目标是使最终的字符串满足不存在下标i j使得s[i] b且s[j] a。求最少删除次数。举个例子输入s aababbab答案是 2。我这里可以手算验证一下原串是a a b a b b a b如果删除第 4 个字符a从 1 开始编号和第 7 个字符a剩下的就是a a b b b b完全合法删除次数是 2有没有可能只删 1 次你试几个位置删掉任何一个字符后剩下的串里仍然能找到ba子序列所以最少就是 2。再比如s bbaaaaabb答案是 2。这个例子也很有意思字符串开头有两个b中间一堆a结尾两个b。最直观的做法是把开头的两个b删掉剩下aaaaabb形状是a* b*合法或者把中间五个a全删了剩下bbbbb也合法但代价是 5。所以最优是删开头的两个b。1.2 “平衡”的等价转化a 必须在 b 前面很多人第一次看到ba子序列这个条件会有点懵其实它等价于一句话所有a都必须出现在所有b的前面。怎么理解假设最终字符串里有一个a出现在某个b的后面那这两个字符按顺序组合起来就是ba这正好违反题目条件。反过来说如果不存在任何a在b后面那就说明所有a的位置都在所有b的位置之前。因此最终的合法字符串只可能是三种情况空串纯a串如aaa纯b串如bbb先是一段a再是一段b如aaabbb。用正则表达式统一表示就是a*b*其中*表示任意数量包括 0 个。这个认知是整个题目的核心后面所有解法都是围绕这个结构展开的。我一开始把条件记反了以为要求所有b在a前面结果样例直接对不上后来才纠正过来。这里顺便提醒一句题目说的“平衡”非常容易和字符串括号匹配、回文、字符计数相等这些概念混淆。它就是字面上的“不出现下降对”本质上是个单调性约束。如果你刷过 Leetcode 926“将字符串翻转到单调递增”会发现这两题的模型几乎一模一样一个是字符a/b一个是0/1最终都是要变成一个单调不减的序列。1.3 为什么暴力枚举行不通最朴素的思路是枚举每个字符删或不删检查剩下的字符串是否合法。长度为n的字符串一共有2^n个子序列这复杂度是指数级的。就算做剪枝把每个合法子序列都检查一遍当n 10^5的时候也完全不可能跑完。再退一步就算不枚举子序列而是考虑“删掉哪些位置的字符”本质上也是一样的组合爆炸。所以这道题必须利用字符串只有a和b两种字符这一强约束。实际上这类“把序列变成单调/平衡结构”的题目十有八九是用动态规划或者贪心因为它们背后的状态空间非常规整。2. 核心解法一动态规划一步步推出来2.1 问题转化删除字符等于保留合法子序列动态规划最忌讳的是盯着“删除”这个操作本身想状态因为删除会改变字符串长度状态不好定义。换个视角删除之后的字符串是原字符串的一个子序列题目要求这个子序列是a*b*形状。那问题就等价于在原串里找一个最长的合法子序列答案就是n - 最长合法子序列长度。这个转化非常重要。它把“删哪些”变成了“留哪些”而“留哪些”天然适合用动态规划做决策从左往右扫描原串对每个字符决定是保留还是删除同时维护当前已经构造出来的子序列是什么状态。这里要特别强调合法子序列必须是a*b*也就是说它有一个状态切换点一开始处于“a 段”可以收a一旦收了第一个b就切换到“b 段”后面只能收b不能再收a。这个“分阶段决策”的感觉就是动态规划状态设计的灵感来源。2.2 状态设计两个 DP 数组表示两种阶段根据上面的分析我们可以把处理过程分为两个阶段阶段 0当前构造出的子序列全是a还没有出现过b阶段 1当前构造出的子序列已经进入b段也就是形如a*b*的合法串。于是定义dp[i][0]处理完s的前i个字符即s[0..i-1]后把它变成一个全 a 串所需的最少删除次数dp[i][1]处理完s的前i个字符后把它变成一个合法 ab串所需的最少删除次数。注意dp[i][1]里说的合法串可以是纯a、纯b也可以是a后面跟b它们都满足题目要求。这里的下标i表示“已经处理了原串前 i 个字符”类似背包问题里的前缀概念是字符串 DP 里最常见的写法。为什么不用一维数组直接定义“删到当前位置为止的最小代价”因为当前位置结束时处于哪个阶段会直接影响后面接新字符时能不能保留。比如后面来了一个a如果前面已经进过b段那这个a就必须删如果前面还在 a 段那就可以留。所以必须用两个状态把“阶段信息”记下来。2.3 状态转移四种情况逐个推现在从i-1推到i设当前新读到的字符是c s[i-1]。分两种情况讨论。情况一c a先看dp[i][0]。我们要把前i个字符变成全a串当前字符正好是a直接保留即可不需要付出删除代价所以dp[i][0] dp[i-1][0]再看dp[i][1]。我们要把前i个字符变成合法串遇到的是a这时候有两条路前i-1个字符被处理成全a串也就是dp[i-1][0]这种状态那当前这个a可以接在全a串后面整体仍然是a*合法代价是dp[i-1][0]前i-1个字符已经被处理成合法a*b*串也就是dp[i-1][1]这种状态这时候如果直接把当前a接上去就可能出现...b...a的结构破坏平衡所以这个a必须删掉代价是dp[i-1][1] 1。取两者较小值dp[i][1] min(dp[i-1][0], dp[i-1][1] 1)这里关键是理解为什么方案 1 用的状态是dp[i-1][0]而不是dp[i-1][1]因为你想保留这个新来的a那前面就不能有任何b已经在合法串里必须要求前面是纯a状态。这是一个容易搞混的细节我在纸上推了两遍才彻底理清。情况二c b先看dp[i][0]。要把前i个字符变成全a串当前字符是b全a串里不能有b所以必须删掉它dp[i][0] dp[i-1][0] 1再看dp[i][1]。要把前i个字符变成合法串遇到的是b这个b是可以直接放进b段的。两条路前i-1个字符被处理成全a串当前b接在末尾整体变成a*b合法前i-1个字符已经被处理成合法a*b*串当前b接在末尾仍然是a*b*也合法。两种情况都不需要删除当前b所以dp[i][1] min(dp[i-1][0], dp[i-1][1])这里要注意dp[i][1]的两个来源都没有1因为b可以直接保留。很多初学者会习惯性写一个1表示删除但这里保留才是最优。2.4 初始化与最终答案dp[0][0]和dp[0][1]都表示空串的情况。空串当然是全a串也是合法的a*b*串所以都初始化为 0。最终答案取min(dp[n][0], dp[n][1])其实dp[n][0]全 a 串也被包含在dp[n][1]的合法范围内但多算一个状态没有坏处而且递推过程中dp[n][0]是dp[n][1]的必要中间状态保留两个能让转移更清晰。最后返回较小值即可。3. 代码落地二维 DP、一维 DP 与复杂度对比3.1 Java 二维 DP 实现思路理顺了代码其实非常短。我先把最直观的二维版本贴出来用 Java 写方便对照class Solution { public int minimumDeletions(String s) { int n s.length(); int[][] dp new int[n 1][2]; for (int i 1; i n; i) { char c s.charAt(i - 1); if (c a) { dp[i][0] dp[i - 1][0]; dp[i][1] Math.min(dp[i - 1][0], dp[i - 1][1] 1); } else { dp[i][0] dp[i - 1][0] 1; dp[i][1] Math.min(dp[i - 1][0], dp[i - 1][1]); } } return Math.min(dp[n][0], dp[n][1]); } }这个版本的代码和上面的推导完全一一对应适合用来对拍验证。它的时间复杂度是 O(n)空间复杂度是 O(n)因为开了一个(n1) x 2的二维数组。3.2 滚动数组优化一维 DP观察一下转移方程dp[i]这一层永远只依赖dp[i-1]这一层和更早的状态没有任何关系。这意味着我们可以用两个变量滚动更新把空间复杂度降到 O(1)。class Solution { public int minimumDeletions(String s) { int keepA 0; // 表示 dp[i-1][0]当前结果为全 a 串的最小删除次数 int keepAB 0; // 表示 dp[i-1][1]当前结果为合法 a*b* 串的最小删除次数 for (char c : s.toCharArray()) { if (c a) { // keepA 不变 keepAB Math.min(keepA, keepAB 1); } else { // 先利用旧的 keepA 和 keepAB 更新 keepAB keepAB Math.min(keepA, keepAB); // 再更新 keepA keepA keepA 1; } } return Math.min(keepA, keepAB); } }这里有一个非常容易踩的坑在c b的分支里必须先更新 keepAB再更新 keepA。因为keepAB Math.min(keepA, keepAB)用到的keepA应该是“前 i-1 个字符变成全 a 串”的旧值如果先把keepA加 1那keepAB里用的就是一个被污染的新值结果会偏大。我第一版一维代码就是栽在这里反复查了几分钟才意识到是更新顺序的问题。3.3 边界条件与自测用例无论哪种实现这几个边界用例都必须过s 答案是 0如果题目允许空串的话s a答案是 0s b答案是 0s ab答案是 0因为本身就是a*b*s ba答案是 1删掉b或删掉a都行s bbaaaaabb答案是 2。我习惯写完代码先用这组小样例手动跑一遍再提交。尤其是ba这种最简单的破坏性用例能快速暴露状态转移里的逻辑漏洞。4. 更快也更好理解的计数法4.1 换个视角最终保留字符串的形状动态规划当然是这道题的标准解法但在面试场景下还有一个更直观、写起来更短的思路枚举分界点。因为最终字符串一定是a...a b...b的形状所以一定存在一个分界位置p使得最终串左边部分只保留a右边部分只保留b。也就是在p左边的字符里所有b都要删掉在p右边的字符里所有a都要删掉p左边剩下的a和p右边剩下的b就组成了最终合法串。因此对任意一个固定的p需要删除的次数就是左边 b 的数量 右边 a 的数量我们从小到大枚举p从 0 到n表示左边包含几个原串前缀字符取这个和的最小值就是答案。4.2 前缀 b 数 后缀 a 数O(n) 时间 O(1) 空间实现上可以先统计整个字符串里a的总数totalA然后从左往右扫描维护两个变量leftB已经扫描过的前缀里b的个数rightA还没扫描到的后缀里a的个数初始值等于totalA。每到一个位置我们把当前这个字符从“右边”划到“左边”如果它是arightA减 1如果它是bleftB加 1。然后计算leftB rightA更新答案。class Solution { public int minimumDeletions(String s) { int totalA 0; for (char c : s.toCharArray()) { if (c a) totalA; } int leftB 0; int rightA totalA; int ans s.length(); // p 0 的情况即所有字符都算在右边 ans Math.min(ans, leftB rightA); for (char c : s.toCharArray()) { if (c a) { rightA--; } else { leftB; } ans Math.min(ans, leftB rightA); } return ans; } }这里循环结束后p实际上遍历了 0 到n的所有分界位置。第一次进循环前先算p0循环里每次把当前位置划入左边后算新的分界点最后一次循环结束后对应pn。这个写法的好处是符合人的直觉反正最终串是左边 a、右边 b我就试试分界线划在哪里最划算。它不需要理解 DP 的阶段概念很多面试者反而更容易想到这个解法。4.3 一次扫描贪心计数法代码只有几行如果继续往下优化可以用一个非常精妙的一次扫描方式。维护两个变量countB当前扫描过的所有b的数量res处理完当前前缀后把它变成合法串所需的最小删除次数。遍历每个字符如果遇到b直接countB因为b可以保留在 b 段里res暂时不变如果遇到a有两个选择把这个a删掉需要的删除次数是res 1保留这个a但这样前面扫描过的所有b都必须删掉需要的删除次数是countB。于是res min(res 1, countB)代码很短class Solution { public int minimumDeletions(String s) { int res 0; int countB 0; for (char c : s.toCharArray()) { if (c b) { countB; } else { res Math.min(res 1, countB); } } return res; } }我拿s aababbab手工跑一遍过程如下遇到ares min(1, 0) 0countB 0遇到ares min(1, 0) 0countB 0遇到bcountB 1遇到ares min(1, 1) 1countB 1遇到bcountB 2遇到bcountB 3遇到ares min(2, 3) 2countB 3遇到bcountB 4最终返回 2和预期一致。4.4 这样贪心为什么是对的可能有朋友会怀疑上面这个一次扫描的式子看起来太简单了真的是严格正确的吗它和动态规划解法其实是相通的。回看动态规划里遇到a时的转移keepAB min(keepA, keepAB 1)在扫描的过程中countB实际上代表的是“如果要从全 a 阶段跳转到 b 阶段前面需要删掉的 b 的个数”。而keepA这个状态在全 a 串里遇到一个b就要累加删除次数它的值恰好等于当前已经扫描过的b的数量。换句话说这里的countB和 DP 里的keepA在数值上是一致的。所以min(res 1, countB) min(keepAB 1, keepA)本质上就是同一个转移方程。一次扫描法没有引入新理论它只不过是把 DP 中两个状态的语义用更直白的方式表达出来了要么删掉当前这个a要么删掉前面所有的b没有第三种选择。4.5 三种方法复杂度对比解法时间复杂度空间复杂度代码量理解难度二维 DPO(n)O(n)中等中等需要理解阶段状态一维滚动 DPO(n)O(1)短比二维稍难注意更新顺序枚举分界点计数O(n)O(1)短直观最好理解一次扫描贪心O(n)O(1)最短需要证明否则不敢写5. 实战避坑卡住我的几个点和相似题对比5.1 我实际提交时踩过的坑先说代码层面。第一个坑是滚动数组的更新顺序前面已经详细说过。c b时必须先用旧值算keepAB再更新keepA。如果你把两条赋值语句顺序写反某些用例答案会偏大而且不是所有用例都错很难一眼发现。第二个坑是Math.min(keepA, keepAB 1)里的1。有个经典错误写法是遇到a时写keepAB Math.min(keepA 1, keepAB)这表示“把当前 a 删掉或者保留但破坏了平衡”逻辑上完全不对。一定要想清楚每一步在描述什么方案 A 是保留当前a前提是前面全a方案 B 是删除当前a代价是在原有合法串基础上加 1。第三个坑是对“子序列”和“子串”的混淆。有的初学者贪图方便想用replace(ba, )或者正则把连续的ba删掉这只能处理连续子串处理不了间隔的子序列。比如abba里面没有连续的ba子串但下标 1 的b和下标 3 的a构成了ba子序列依然不合法。这种题目必须从子序列约束的角度去理解不能用字符串替换的思路硬套。5.2 构造自测用例的经验刷题时如果测试用例没覆盖全很容易带着隐藏 bug 提交。我现在遇到这种字符串 DP 题会专门构造几类用例全同字符aaaa和bbbb答案都应该是 0本身合法aaabbb答案 0完全反序bbbaaa答案 3因为要么删掉左边 3 个b要么删掉右边 3 个a交替串ababab这个我建议手动算一遍答案是 3单字符边界a、b答案都是 0。把这些用例放在本地跑一遍基本上能把 DP 转移、边界初始化这些环节验证过。尤其建议跑一下交替串因为交替串对分界点和“删 a 还是删 b”的决策非常敏感很容易暴露状态设计里的漏洞。5.3 相似题对比Leetcode 926 与后续扩展如果你做过 Leetcode 926“将字符串翻转到单调递增”会发现它和这题几乎是一个模子刻出来的。926 题给的是二进制字符串要求通过翻转字符0 变 1 或 1 变 0使最终字符串单调不减求最少翻转次数。这里的“单调不减”放在a/b世界里就是“所有 a 在 b 前面”也就是本题的平衡条件。两道题都能用同一种 DP 模板解状态都是“当前处于 0 段还是 1 段”转移都是按当前字符分四个分支。甚至 926 也可以枚举分界点左边全变 0、右边全变 1代价是左边 1 的个数加右边 0 的个数。把这两题放在一起对比刷比单独刷一道效果要好得多因为它们共享同一套思考框架。更进一步的扩展是把字符集变大比如给定多个字符要求最终字符串按某种字典序排列那就是更复杂的序列对齐问题了。不过面试基本不会考到那么深能把a/b两种字符的模型讲清楚已经足以应对大部分动态规划入门问题。回到这题本身我个人最大的体会是最直观的解法不一定是最容易写对的解法。枚举分界点的计数法思路简单但边界处理要小心一次扫描贪心代码最短但如果不理解它为什么等价于 DP面试时被追问很容易露怯。所以我建议准备这道题时把一维 DP 和计数法都写一遍然后用计数法做最终提交用 DP 证明正确性。这样既显得思路全面又不至于让代码显得太玄学。最后再分享一个小技巧凡是遇到“删除最少字符使序列满足单调性/平衡性”的题目优先往“分界点”方向想。只要最终结构有一个固定的分界点枚举分界点往往就是 O(n) 的解法而且正确性比花哨的贪心更容易解释。 先交代一下背景这道题我是在整理字符串类动态规划题目的时候重新刷到的。Leetcode 1653题名很直白使字符串平衡的最少删除次数。给定一个只包含字符a和b的字符串s每次可以删除任意一个字符问最少删除多少个字符能让剩下的字符串变成“平衡”的。这里的平衡定义非常微妙它不是说a和b的数量一样多也不是什么括号匹配而是剩下的字符串中不能出现ba这个子序列也就是说字符串里一旦出现了b那后面就不能再出现a。直白点讲最终合法的字符串一定是形如若干a后面跟着若干b也就是正则表达式a*b*的结构。这个题非常适合用来练动态规划也能引申出多种解法从二维 DP 到一维滚动数组再到 O(n) 的一次扫描贪心一层层优化下来非常有意思。我刚接触这道题的时候第一反应是暴力枚举删除哪些字符马上意识到不可能字符串长度最高能到十万级别每个字符删或不删就是 2 的 N 次方种方案直接爆炸。后来老老实实从“合法子序列”的角度想才发现这题本质上是在找一个最长的、形状为a*b*的子序列然后用总长度减掉它就是最少删除次数。这篇文章我把整个思考过程、三种主流解法、还有我实际提交时踩过的几个坑都写下来给准备面试或者刷动态规划的朋友做个参考。1. 看懂题目字符串平衡到底在说什么1.1 原题描述与示例回顾先把题目的原始定义摆出来。给定字符串s只含小写字母a和b每次操作可以从s中删除任意一个字符。目标是使最终的字符串满足不存在下标i j使得s[i] b且s[j] a。求最少删除次数。举个例子输入s aababbab答案是 2。我这里可以手算验证一下原串是a a b a b b a b如果删除第 4 个字符a从 1 开始编号和第 7 个字符a剩下的就是a a b b b b完全合法删除次数是 2有没有可能只删 1 次你试几个位置删掉任何一个字符后剩下的串里仍然能找到ba子序列所以最少就是 2。再比如s bbaaaaabb答案是 2。这个例子也很有意思字符串开头有两个b中间一堆a结尾两个b。最直观的做法是把开头的两个b删掉剩下aaaaabb形状是a* b*合法或者把中间五个a全删了剩下bbbbb也合法但代价是 5。所以最优是删开头的两个b。1.2 “平衡”的等价转化a 必须在 b 前面很多人第一次看到ba子序列这个条件会有点懵其实它等价于一句话所有a都必须出现在所有b的前面。怎么理解假设最终字符串里有一个a出现在某个b的后面那这两个字符按顺序组合起来就是ba这正好违反题目条件。反过来说如果不存在任何a在b后面那就说明所有a的位置都在所有b的位置之前。因此最终的合法字符串只可能是三种情况空串纯a串如aaa纯b串如bbb先是一段a再是一段b如aaabbb。用正则表达式统一表示就是a*b*其中*表示任意数量包括 0 个。这个认知是整个题目的核心后面所有解法都是围绕这个结构展开的。我一开始把条件记反了以为要求所有b在a前面结果样例直接对不上后来才纠正过来。这里顺便提醒一句题目说的“平衡”非常容易和字符串括号匹配、回文、字符计数相等这些概念混淆。它就是字面上的“不出现下降对”本质上是个单调性约束。如果你刷过 Leetcode 926“将字符串翻转到单调递增”会发现这两题的模型几乎一模一样一个是字符a/b一个是0/1最终都是要变成一个单调不减的序列。1.3 为什么暴力枚举行不通最朴素的思路是枚举每个字符删或不删检查剩下的字符串是否合法。长度为n的字符串一共有2^n个子序列这复杂度是指数级的。就算做剪枝把每个合法子序列都检查一遍当n 10^5的时候也完全不可能跑完。再退一步就算不枚举子序列而是考虑“删掉哪些位置的字符”本质上也是一样的组合爆炸。所以这道题必须利用字符串只有a和b两种字符这一强约束。实际上这类“把序列变成单调/平衡结构”的题目十有八九是用动态规划或者贪心因为它们背后的状态空间非常规整。2. 核心解法一动态规划一步步推出来2.1 问题转化删除字符等于保留合法子序列动态规划最忌讳的是盯着“删除”这个操作本身想状态因为删除会改变字符串长度状态不好定义。换个视角删除之后的字符串是原字符串的一个子序列题目要求这个子序列是a*b*形状。那问题就等价于在原串里找一个最长的合法子序列答案就是n - 最长合法子序列长度。这个转化非常重要。它把“删哪些”变成了“留哪些”而“留哪些”天然适合用动态规划做决策从左往右扫描原串对每个字符决定是保留还是删除同时维护当前已经构造出来的子序列是什么状态。这里要特别强调合法子序列必须是a*b*也就是说它有一个状态切换点一开始处于“a 段”可以收a一旦收了第一个b就切换到“b 段”后面只能收b不能再收a。这个“分阶段决策”的感觉就是动态规划状态设计的灵感来源。2.2 状态设计两个 DP 数组表示两种阶段根据上面的分析我们可以把处理过程分为两个阶段阶段 0当前构造出的子序列全是a还没有出现过b阶段 1当前构造出的子序列已经进入b段也就是形如a*b*的合法串。于是定义dp[i][0]处理完s的前i个字符即s[0..i-1]后把它变成一个全 a 串所需的最少删除次数dp[i][1]处理完s的前i个字符后把它变成一个合法 ab串所需的最少删除次数。注意dp[i][1]里说的合法串可以是纯a、纯b也可以是a后面跟b它们都满足题目要求。这里的下标i表示“已经处理了原串前 i 个字符”类似背包问题里的前缀概念是字符串 DP 里最常见的写法。为什么不用一维数组直接定义“删到当前位置为止的最小代价”因为当前位置结束时处于哪个阶段会直接影响后面接新字符时能不能保留。比如后面来了一个a如果前面已经进过b段那这个a就必须删如果前面还在 a 段那就可以留。所以必须用两个状态把“阶段信息”记下来。2.3 状态转移四种情况逐个推现在从i-1推到i设当前新读到的字符是c s[i-1]。分两种情况讨论。情况一c a先看dp[i][0]。我们要把前i个字符变成全a串当前字符正好是a直接保留即可不需要付出删除代价所以dp[i][0] dp[i-1][0]再看dp[i][1]。我们要把前i个字符变成合法串遇到的是a这时候有两条路前i-1个字符被处理成全a串也就是dp[i-1][0]这种状态那当前这个a可以接在全a串后面整体仍然是a*合法代价是dp[i-1][0]前i-1个字符已经被处理成合法a*b*串也就是dp[i-1][1]这种状态这时候如果直接把当前a接上去就可能出现...b...a的结构破坏平衡所以这个a必须删掉代价是dp[i-1][1] 1。取两者较小值dp[i][1] min(dp[i-1][0], dp[i-1][1] 1)这里关键是理解为什么方案 1 用的状态是dp[i-1][0]而不是dp[i-1][1]因为你想保留这个新来的a那前面就不能有任何b已经在合法串里必须要求前面是纯a状态。这是一个容易搞混的细节我在纸上推了两遍才彻底理清。情况二c b先看dp[i][0]。要把前i个字符变成全a串当前字符是b全a串里不能有b所以必须删掉它dp[i][0] dp[i-1][0] 1再看dp[i][1]。要把前i个字符变成合法串遇到的是b这个b是可以直接放进b段的。两条路前i-1个字符被处理成全a串当前b接在末尾整体变成a*b合法前i-1个字符已经被处理成合法a*b*串当前b接在末尾仍然是a*b*也合法。两种情况都不需要删除当前b所以dp[i][1] min(dp[i-1][0], dp[i-1][1])这里要注意dp[i][1]的两个来源都没有1因为b可以直接保留。很多初学者会习惯性写一个1表示删除但这里保留才是最优。2.4 初始化与最终答案dp[0][0]和dp[0][1]都表示空串的情况。空串当然是全a串也是合法的a*b*串所以都初始化为 0。最终答案取min(dp[n][0], dp[n][1])其实dp[n][0]全 a 串也被包含在dp[n][1]的合法范围内但多算一个状态没有坏处而且递推过程中dp[n][0]是dp[n][1]的必要中间状态保留两个能让转移更清晰。最后返回较小值即可。3. 代码落地二维 DP、一维 DP 与复杂度对比3.1 Java 二维 DP 实现思路理顺了代码其实非常短。我先把最直观的二维版本贴出来用 Java 写方便对照class Solution { public int minimumDeletions(String s) { int n s.length(); int[][] dp new int[n 1][2]; for (int i 1; i n; i) { char c s.charAt(i - 1); if (c a) { dp[i][0] dp[i - 1][0]; dp[i][1] Math.min(dp[i - 1][0], dp[i - 1][1] 1); } else { dp[i][0] dp[i - 1][0] 1; dp[i][1] Math.min(dp[i - 1][0], dp[i - 1][1]); } } return Math.min(dp[n][0], dp[n][1]); } }这个版本的代码和上面的推导完全一一对应适合用来对拍验证。它的时间复杂度是 O(n)空间复杂度是 O(n)因为开了一个(n1) x 2的二维数组。3.2 滚动数组优化一维 DP观察一下转移方程dp[i]这一层永远只依赖dp[i-1]这一层和更早的状态没有任何关系。这意味着我们可以用两个变量滚动更新把空间复杂度降到 O(1)。class Solution { public int minimumDeletions(String s) { int keepA 0; // 表示 dp[i-1][0]当前结果为全 a 串的最小删除次数 int keepAB 0; // 表示 dp[i-1][1]当前结果为合法 a*b* 串的最小删除次数 for (char c : s.toCharArray()) { if (c a) { // keepA 不变 keepAB Math.min(keepA, keepAB 1); } else { // 先利用旧的 keepA 和 keepAB 更新 keepAB keepAB Math.min(keepA, keepAB); // 再更新 keepA keepA keepA 1; } } return Math.min(keepA, keepAB); } }这里有一个非常容易踩的坑在c b的分支里必须先更新 keepAB再更新 keepA。因为keepAB Math.min(keepA, keepAB)用到的keepA应该是“前 i-1 个字符变成全 a 串”的旧值如果先把keepA加 1那keepAB里用的就是一个被污染的新值结果会偏大。我第一版一维代码就是栽在这里反复查了几分钟才意识到是更新顺序的问题。3.3 边界条件与自测用例无论哪种实现这几个边界用例都必须过s 答案是 0如果题目允许空串的话s a答案是 0s b答案是 0s ab答案是 0因为本身就是a*b*s ba答案是 1删掉b或删掉a都行s bbaaaaabb答案是 2。我习惯写完代码先用这组小样例手动跑一遍再提交。尤其是ba这种最简单的破坏性用例能快速暴露状态转移里的逻辑漏洞。4. 更快也更好理解的计数法4.1 换个视角最终保留字符串的形状动态规划当然是这道题的标准解法但在面试场景下还有一个更直观、写起来更短的思路枚举分界点。因为最终字符串一定是a...a b...b的形状所以一定存在一个分界位置p使得最终串左边部分只保留a右边部分只保留b。也就是在p左边的字符里所有b都要删掉在p右边的字符里所有a都要删掉p左边剩下的a和p右边剩下的b就组成了最终合法串。因此对任意一个固定的p需要删除的次数就是左边 b 的数量 右边 a 的数量我们从小到大枚举p从 0 到n表示左边包含几个原串前缀字符取这个和的最小值就是答案。4.2 前缀 b 数 后缀 a 数O(n) 时间 O(1) 空间实现上可以先统计整个字符串里a的总数totalA然后从左往右扫描维护两个变量leftB已经扫描过的前缀里b的个数rightA还没扫描到的后缀里a的个数初始值等于totalA。每到一个位置我们把当前这个字符从“右边”划到“左边”如果它是arightA减 1如果它是bleftB加 1。然后计算leftB rightA更新答案。class Solution { public int minimumDeletions(String s) { int totalA 0; for (char c : s.toCharArray()) { if (c a) totalA; } int leftB 0; int rightA totalA; int ans s.length(); // p 0 的情况即所有字符都算在右边 ans Math.min(ans, leftB rightA); for (char c : s.toCharArray()) { if (c a) { rightA--; } else { leftB; } ans Math.min(ans, leftB rightA); } return ans; } }这里循环结束后p实际上遍历了 0 到n的所有分界位置。第一次进循环前先算p0循环里每次把当前位置划入左边后算新的分界点最后一次循环结束后对应pn。这个写法的好处是符合人的直觉反正最终串是左边 a、右边 b我就试试分界线划在哪里最划算。它不需要理解 DP 的阶段概念很多面试者反而更容易想到这个解法。4.3 一次扫描贪心计数法代码只有几行如果继续往下优化可以用一个非常精妙的一次扫描方式。维护两个变量countB当前扫描过的所有b的数量res处理完当前前缀后把它变成合法串所需的最小删除次数。遍历每个字符如果遇到b直接countB因为b可以保留在 b 段里res暂时不变如果遇到a有两个选择把这个a删掉需要的删除次数是res 1保留这个a但这样前面扫描过的所有b都必须删掉需要的删除次数是countB。于是res min(res 1, countB)代码很短class Solution { public int minimumDeletions(String s) { int res 0; int countB 0; for (char c : s.toCharArray()) { if (c b) { countB; } else { res Math.min(res 1, countB); } } return res; } }我拿s aababbab手工跑一遍过程如下遇到ares min(1, 0) 0countB 0遇到ares min(1, 0) 0countB 0遇到bcountB 1遇到ares min(1, 1) 1countB 1遇到bcountB 2遇到bcountB 3遇到ares min(2, 3) 2countB 3遇到bcountB 4最终返回 2和预期一致。4.4 这样贪心为什么是对的可能有朋友会怀疑上面这个一次扫描的式子看起来太简单了真的是严格正确的吗它和动态规划解法其实是相通的。回看动态规划里遇到a时的转移keepAB min(keepA, keepAB 1)在扫描的过程中countB实际上代表的是“如果要从全 a 阶段跳转到 b 阶段前面需要删掉的 b 的个数”。而keepA这个状态在全 a 串里遇到一个b就要累加删除次数它的值恰好等于当前已经扫描过的b的数量。换句话说这里的countB和 DP 里的keepA在数值上是一致的。所以min(res 1, countB) min(keepAB 1, keepA)本质上就是同一个转移方程。一次扫描法没有引入新理论它只不过是把 DP 中两个状态的语义用更直白的方式表达出来了要么删掉当前这个a要么删掉前面所有的b没有第三种选择。4.5 三种方法复杂度对比解法时间复杂度空间复杂度代码量理解难度二维 DPO(n)O(n)中等中等需要理解阶段状态一维滚动 DPO(n)O(1)短比二维稍难注意更新顺序枚举分界点计数O(n)O(1)短直观最好理解一次扫描贪心O(n)O(1)最短需要证明否则不敢写5. 实战避坑卡住我的几个点和相似题对比5.1 我实际提交时踩过的坑先说代码层面。第一个坑是滚动数组的更新顺序前面已经详细说过。c b时必须先用旧值算keepAB再更新keepA。如果你把两条赋值语句顺序写反某些用例答案会偏大而且不是所有用例都错很难一眼发现。第二个坑是Math.min(keepA, keepAB 1)里的1。有个经典错误写法是遇到a时写keepAB Math.min(keepA 1, keepAB)这表示“把当前 a 删掉或者保留但破坏了平衡”逻辑上完全不对。一定要想清楚每一步在描述什么方案 A 是保留当前a前提是前面全a方案 B 是删除当前a代价是在原有合法串基础上加 1。第三个坑是对“子序列”和“子串”的混淆。有的初学者贪图方便想用replace(ba, )或者正则把连续的ba删掉这只能处理连续子串处理不了间隔的子序列。比如abba里面没有连续的ba子串但下标 1 的b和下标 3 的a构成了ba子序列依然不合法。这种题目必须从子序列约束的角度去理解不能用字符串替换的思路硬套。5.2 构造自测用例的经验刷题时如果测试用例没覆盖全很容易带着隐藏 bug 提交。我现在遇到这种字符串 DP 题会专门构造几类用例全同字符aaaa和bbbb答案都应该是 0本身合法aaabbb答案 0完全反序bbbaaa答案 3因为要么删掉左边 3 个b要么删掉右边 3 个a交替串ababab这个我建议手动算一遍答案是 3单字符边界a、b答案都是 0。把这些用例放在本地跑一遍基本上能把 DP 转移、边界初始化这些环节验证过。尤其建议跑一下交替串因为交替串对分界点和“删 a 还是删 b”的决策非常敏感很容易暴露状态设计里的漏洞。5.3 相似题对比Leetcode 926 与后续扩展如果你做过 Leetcode 926“将字符串翻转到单调递增”会发现它和这题几乎是一个模子刻出来的。926 题给的是二进制字符串要求通过翻转字符0 变 1 或 1 变 0使最终字符串单调不减求最少翻转次数。这里的“单调不减”放在a/b世界里就是“所有 a 在 b 前面”也就是本题的平衡条件。两道题都能用同一种 DP 模板解状态都是“当前处于 0 段还是 1 段”转移都是按当前字符分四个分支。甚至 926 也可以枚举分界点左边全变 0、右边全变 1代价是左边 1 的个数加右边 0 的个数。把这两题放在一起对比刷比单独刷一道效果要好得多因为它们共享同一套思考框架。更进一步的扩展是把字符集变大比如给定多个字符要求最终字符串按某种字典序排列那就是更复杂的序列对齐问题了。不过面试基本不会考到那么深能把a/b两种字符的模型讲清楚已经足以应对大部分动态规划入门问题。回到这题本身我个人最大的体会是最直观的解法不一定是最容易写对的解法。枚举分界点的计数法思路简单但边界处理要小心一次扫描贪心代码最短但如果不理解它为什么等价于 DP面试时被追问很容易露怯。所以我建议准备这道题时把一维 DP 和计数法都写一遍然后用计数法做最终提交用 DP 证明正确性。这样既显得思路全面又不至于让代码显得太玄学。最后再分享一个小技巧凡是遇到“删除最少字符使序列满足单调性/平衡性”的题目优先往“分界点”方向想。只要最终结构有一个固定的分界点枚举分界点往往就是 O(n) 的解法而且正确性比花哨的贪心更容易解释。