ヒント → https://atcoder.jp/contests/agc066/editorial/9634

[1] 最適解の構造

操作後の文字列を \(T\) とします．

\(S, T\) ともに末尾に B を足して考えることにすると，\(T\) は B と AB を並べたものと考えることができます．

\(T\) において隣接する B, AB をスワップするという操作を考えることにより，最適な \(T\) の構造を考えましょう．

\(T\) が最適解であるとします．\(T\) において B, AB がこの順に並ぶ部分 BAB について，この A の初期位置がこの位置よりも左であるとすると，AB, B を入れ替えることでコストを減らすことができます．\(T\) において AB, B がこの順に並ぶ部分 ABB について，この A の初期位置がこの位置よりも右であるとすると，AB, B を入れ替えることでコストを減らすことができます．

すると，最適解 \(T\) を AB, B に分解したときに，B の前後の位置を通る A は存在しないことが分かります．

[2] 動的計画法による答の計算

以上の観察に基づいて，dp による解法を設計しましょう．

\(\mathrm{dp}[i]\) は，AB, B からなる長さ \(i\) の文字列を \(S\) の先頭 \(i\) 文字だけから（\(i,i+1\) 文字目の間のスワップをせずに）作るときの最小コストとします．

まず，\(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\) が存在しない遷移だけを考えればよいです．

以上により，dp の状態の個数，遷移の個数がともに \(O(N)\) にできました．

\(i<k<j\) かつ \(\mathrm{sum}[i] = \mathrm{sum}[k]=\mathrm{sum}[j]\) となる \(k\) が存在しないときには，この間に並べる AB について，左から来る A と右から来る A が両方は存在しないことも簡単に分かります．したがって，各遷移のコストは適当な累積和の前計算により \(O(1)\) 時間で計算できます．