我们将操作后的字符串称为 T。通过在 S 和 T 的末尾添加 B，我们可以认为 T 是 B 和 AB 的排列。通过考虑在 T 中相邻的 B 和 AB 交换的操作，我们来分析最优的 T 的结构。假设 T 是最优解，对于部分 BAB，如果这个 A 的初始位置在这个位置的左侧，则通过交换 AB 和 B 可以降低成本。对于部分 ABB，如果这个 A 的初始位置在这个位置的右侧，则同样可以通过交换 AB 和 B 降低成本。
由此可知，当将最优解 T 分解为 AB 和 B 时，B 前后位置之间不会存在 A。
[2] 动态规划求解
基于以上观察，我们设计一个动态规划的解法。我们定义 \mathrm{dp}[i] 为用 S 的前 i 个字符（不进行 i 和 i+1 之间的交换）构造由 AB 和 B 组成的长度为 i 的字符串的最小成本。
首先，如果 S 的第 i 个字符是 B，则可以有转移 \mathrm{dp}[i] \leftarrow \mathrm{dp}[i-1]。
在排列 AB 的部分，我们这样处理。首先定义 \mathrm{sum}[i]：这是 S 的前 i 个字符中 B 的数量减去 A 的数量。因此在满足 i < j 且 \mathrm{sum}[i] = \mathrm{sum}[j] 时，我们可以用 AB 来从 \mathrm{dp}[i] 转移到 \mathrm{dp}[j]。对任意满足 i < k < j 且 \mathrm{sum}[i] = \mathrm{sum}[k] = \mathrm{sum}[j] 的 i, k, j，从 \mathrm{dp}[i] 到 \mathrm{dp}[j] 的转移可以分解为从 \mathrm{dp}[i] 到 \mathrm{dp}[k]，然后再从 \mathrm{dp}[k] 到 \mathrm{dp}[j] 的转移。因此我们只需考虑那些不存在这样的 k 的转移。
综上所述，动态规划状态的数量和转移的数量都可以做到 O(N)。当不存在满足 i < k < j 且 \mathrm{sum}[i] = \mathrm{sum}[k] = \mathrm{sum}[j] 的 k 时，可以很容易得出在此之间排列的 AB 中，来自左侧和右侧的 A 不会同时存在。因此，每个转移的成本可以通过适当的前缀和预处理在 O(1) 时间内计算出来。