使字符串平衡的最少删除次数 图解题解
这道题到底在问什么
- 输入
- s="aababbab"
- 输出
- 2 (删 2 个字符即可平衡)
- 输入
- s="bbaaaaabb"
- 输出
- 2 (删掉最前面的两个 b)
- 输入
- s="aaaa"
- 输出
- 0 (已经平衡,无需删)
最优解：一步一步想明白
- 3记住这套「见 b 就 b+1、见 a 就 dp = min(dp+1, b)」,下面每一帧都在套它。这里 b 是「已扫描到的 b 总数」,不是最终保留多少 b。
- 4开局:还没扫任何字符,已扫描到的 b 总数 b=0,最少删除数 dp=0。指针停在第 0 个字符 b 上准备处理。
- 5看第 0 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。
- 6这一步只把已扫描的 b 总数加 1,记到 1 个,本步不产生删除代价。dp 不变,仍是 0。是否要删掉这些 b,留到后面遇到 a 时再权衡。
- 7看第 1 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。
- 8这一步只把已扫描的 b 总数加 1,记到 2 个,本步不产生删除代价。dp 不变,仍是 0。是否要删掉这些 b,留到后面遇到 a 时再权衡。
- 9看第 2 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。
- 10比较两条路:删掉这个 a 花 1,删掉已扫描的 2 个 b 花 2。这一帧「删这个 a」更省(1 < 2),临时标红示意。dp 只记录最少代价 1,并不锁定最终一定删它,后面若有更优方案仍会改写。
- 11看第 3 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。
- 12比较两条路:删掉这个 a 花 2,删掉已扫描的 2 个 b 花 2。两条路打平(2 = 2),任选一种都行;这里临时按删这个 a 标红示意。dp 取这个最少代价 2,并不锁定最终一定删它,后面若有更优方案仍会改写。
- 13看第 4 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。
- 14比较两条路:删掉这个 a 花 3,删掉已扫描的 2 个 b 花 2。这一帧「删前面的 b」更省(2 < 3),当前 a 暂按保留标绿示意。dp 只记录最少代价 2,不锁定最终删除路径。
- 15看第 5 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。
- 16比较两条路:删掉这个 a 花 3,删掉已扫描的 2 个 b 花 2。这一帧「删前面的 b」更省(2 < 3),当前 a 暂按保留标绿示意。dp 只记录最少代价 2,不锁定最终删除路径。
- 17看第 6 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。
- 18比较两条路:删掉这个 a 花 3,删掉已扫描的 2 个 b 花 2。这一帧「删前面的 b」更省(2 < 3),当前 a 暂按保留标绿示意。dp 只记录最少代价 2,不锁定最终删除路径。
- 19看第 7 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。
- 20这一步只把已扫描的 b 总数加 1,记到 3 个,本步不产生删除代价。dp 不变,仍是 2。是否要删掉这些 b,留到后面遇到 a 时再权衡。
- 21看第 8 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。
- 22这一步只把已扫描的 b 总数加 1,记到 4 个,本步不产生删除代价。dp 不变,仍是 2。是否要删掉这些 b,留到后面遇到 a 时再权衡。
- 23全程扫完,dp 收在 2,这就是最少删除次数。它只给出代价数字,不指定唯一删法;对 "bbaaaaabb" 来说,删掉开头那两个 b 得到 "aaaaabb" 是其中一种达到 2 次的平衡方案。
⚠️ 容易写错的地方
✗ 错：遇到 b 时也去更新 dp
✓ 对：只让已扫描的 b 计数自增,dp 不动
这一步本身不删任何字符,代价为 0,是否删这些 b 等遇到 a 再算
✗ 错：遇到 a 只想着删这个 a
✓ 对：还要和「删掉已扫描的所有 b」比,取较小
已扫描的 b 很少时,删光那几个 b 比一路删 a 更省
✗ 错：把平衡理解成 a、b 个数相等
✓ 对：平衡是「a 全在 b 左边」,与个数无关
"aaab" 已平衡,答案是 0,跟数量是否相等无关
完整代码（Python / C++ / Java）
Python
class Solution:
def minimumDeletions(self, s: str) -> int:
b = dp = 0
for ch in s:
if ch == 'b':
b += 1
else:
dp = min(dp + 1, b)
return dpC++
#include <algorithm>
#include <string>
using namespace std;
class Solution {
public:
int minimumDeletions(string s) {
int b = 0, dp = 0;
for (char c : s) {
if (c == 'b') b++;
else dp = min(dp + 1, b);
}
return dp;
}
};Java
import java.util.*;
class Solution {
public int minimumDeletions(String s) {
int b = 0, dp = 0;
for (char c : s.toCharArray()) {
if (c == 'b') b++;
else dp = Math.min(dp + 1, b);
}
return dp;
}
}复杂度
时间
O(n)
从头到尾扫一遍字符串
空间
O(1)
只用 b、dp 两个整数变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使字符串平衡的最少删除次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么贪心(直接 dp = min(dp+1, b))就一定最优,不会漏更好的方案?+
dp 的定义是「让前缀 s[0..i] 平衡的最少删除数」。新来一个 a,合法状态只有两种:它留在前段(必须把已扫描到的 b 全删,故接到 b 上)或它被删(接到 dp 上加 1)。两种情况覆盖了所有可能,取最小即得该前缀的最优,因此整体最优。这就是标准的线性 DP。
如果字符不止 a、b 两种,思路还能用吗?+
核心思想可推广:这其实是「最少删除使序列单调不降」的特例。一般情况可转成「保留最长不下降子序列、删掉其余」,用 O(n log n) 的 LIS 变形求解。只有两种字符时退化成本题的 O(n) 贪心。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 使字符串平衡的最少删除次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。