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

记住这套「见 b 就 b+1、见 a 就 dp = min(dp+1, b)」,下面每一帧都在套它。这里 b 是「已扫描到的 b 总数」,不是最终保留多少 b。

开局:还没扫任何字符,已扫描到的 b 总数 b=0,最少删除数 dp=0。指针停在第 0 个字符 b 上准备处理。

看第 0 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。

这一步只把已扫描的 b 总数加 1,记到 1 个,本步不产生删除代价。dp 不变,仍是 0。是否要删掉这些 b,留到后面遇到 a 时再权衡。

看第 1 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。

这一步只把已扫描的 b 总数加 1,记到 2 个,本步不产生删除代价。dp 不变,仍是 0。是否要删掉这些 b,留到后面遇到 a 时再权衡。

看第 2 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。

比较两条路:删掉这个 a 花 1,删掉已扫描的 2 个 b 花 2。这一帧「删这个 a」更省(1 < 2),临时标红示意。dp 只记录最少代价 1,并不锁定最终一定删它,后面若有更优方案仍会改写。

看第 3 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。

比较两条路:删掉这个 a 花 2,删掉已扫描的 2 个 b 花 2。两条路打平(2 = 2),任选一种都行;这里临时按删这个 a 标红示意。dp 取这个最少代价 2,并不锁定最终一定删它,后面若有更优方案仍会改写。

看第 4 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。

比较两条路:删掉这个 a 花 3,删掉已扫描的 2 个 b 花 2。这一帧「删前面的 b」更省(2 < 3),当前 a 暂按保留标绿示意。dp 只记录最少代价 2,不锁定最终删除路径。

看第 5 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。

比较两条路:删掉这个 a 花 3,删掉已扫描的 2 个 b 花 2。这一帧「删前面的 b」更省(2 < 3),当前 a 暂按保留标绿示意。dp 只记录最少代价 2,不锁定最终删除路径。

看第 6 个字符,是 a。a 想合法留在前段,就得删掉已扫描到的所有 b;要么干脆删掉这个 a。

比较两条路:删掉这个 a 花 3,删掉已扫描的 2 个 b 花 2。这一帧「删前面的 b」更省(2 < 3),当前 a 暂按保留标绿示意。dp 只记录最少代价 2,不锁定最终删除路径。

看第 7 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。

这一步只把已扫描的 b 总数加 1,记到 3 个,本步不产生删除代价。dp 不变,仍是 2。是否要删掉这些 b,留到后面遇到 a 时再权衡。

看第 8 个字符,是 b。先把已扫描的 b 总数计上一笔,后面 a 要不要删它再说。

这一步只把已扫描的 b 总数加 1,记到 4 个,本步不产生删除代价。dp 不变,仍是 2。是否要删掉这些 b,留到后面遇到 a 时再权衡。

全程扫完,dp 收在 2,这就是最少删除次数。它只给出代价数字,不指定唯一删法;对 "bbaaaaabb" 来说,删掉开头那两个 b 得到 "aaaaabb" 是其中一种达到 2 次的平衡方案。

边界先想清:单字符、全 a、全 b 都是 0;只有 b 真正挡住了 a 才需删。

两个高频追问:为什么贪心最优、以及如何推广到多字符。