使字符串平衡的最少删除次数 图解题解

「平衡」到底要求字符串长成什么样

给一个只含 a 和 b 的字符串 s，删最少的字符，让删完后不存在任何一个 b 排在某个 a 的左边，也就是整个串成「先一串 a，再一串 b」的形状（某段为空也算）。例如 s="bbaaaaabb"，删掉开头两个 b 得 "aaaaabb" 恰好平衡，删了 2 个；s="aaaa" 本就平衡，一个都不用删。

为什么不能把「删哪些字符」逐种试过去

一个长度 n 的串，每个字符删或不删，删法共 2ⁿ 种，n 到几十就数不完，逐种试再检查显然不行。突破口是：平衡串被限定成「a 在前、b 在后」，所以从左往右扫时，每个字符要不要留，只取决于「到目前已付出多少删除代价」和「前面积攒了几个 b」这两个量，不必回头重算。

扫到一半时，只要记住哪两个数

顺着串从左扫到右，只要维护两个数。第一个是 dp，存的是「到当前字符为止、让已扫过的这段前缀变平衡，最少得删几个字符」；把这个前缀的答案一路记下来、下个字符接着用它推新值，正是动态规划。第二个是 b：已经扫过的 b 的总个数，不是最终保留几个 b。开局两个都是 0。

遇到一个 a，是删它自己还是删它前面所有 b

扫到的字符是 b 时好办：b 只可能待在后段，先记进「已扫描的 b 总数」，本步不产生删除代价，dp 原封不动。要做决定的是扫到 a 时。这个 a 想留在前段，就得让它左边一个 b 都不剩，于是只有两条路：删掉它前面已扫到的全部 b，代价是 b——选这条路等于留这个 a 和前面所有 a、只删所有 b，本身就是这段前缀的完整方案，代价恰是 b、与旧 dp 无关；或把这个 a 自己删掉，代价是原来 dp 再加 1，即 dp+1。哪条省走哪条，所以 dp=min(dp+1, b)。

这一步的 min 才是全题做决定的地方（min 取两者中较小）：dp+1 是「留前面的 b、牺牲这个 a」，b 是「留这个 a、清掉前面所有 b」。

拿 s="bbaaaaabb" 把 dp 一步步逼出来

起手 b=0、dp=0。先是两个 b：b 依次记到 1、2，dp 一直是 0。接着五个 a：第一个 a，dp=min(dp+1, b)=min(0+1, 2)=1，删自己更省；第二个 a，dp=min(1+1, 2)=2，两条打平；第三个 a，dp=min(2+1, 2)=2，这回删前面两个 b 更省；第四、第五个 a 都是 min(3, 2)=2，dp 稳在 2。最后两个 b：b 记到 3、4，dp 不动。扫完 dp=2 即答案，对应删掉开头那两个 b。

全 a 或全 b 的串，答案为什么直接是 0

有人把「遇到 b」也当成付代价的一步，急着扫到 b 就删，dp 就被算大了；其实遇到 b 只是计数、零代价，dp 一个字都不改，删不删要留到后面遇到 a 才结算。复杂度很轻：从头到尾只扫一遍，时间 O(n)（大 O 记号，描述规模变大时操作数怎么涨，n 是串长）；只用 b、dp 两个整数，空间 O(1)（占用和串长无关）。

边界也顺带想清：单个字符、全是 a、全是 b，这三种串本身就平衡，dp 没机会变大，答案都是 0；只有当某个 b 真挡在某个 a 前面时才需要删。

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 dp

C++

#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;
    }
}