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

---

[1] 方針

消せずに残る文字の個数を最小化することを考えます． \(\mathrm{dp}[i]\) を，\(S\) の先頭 \(i\) 文字に対して操作を行ったときに消せずに残る文字の個数の最小値とします．

おおよそ次のような計算をすればよいことになります：

• \(i\) 文字目を消さない場合：\(\mathrm{dp}[i+1]\leftarrow \mathrm{dp}[i]+1\)．
• \(i+1\) 文字目から \(j\) 文字目までを消す場合：\(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\)．

2 番目の遷移がどのようなものかを考えましょう．そのためには，ある文字列が操作により消せる（空文字列にできる）のはどういうときかを考えればよいです．

---

[2] 文字列が消せるための条件

次が成り立ちます：

• 文字列 \(S\) が操作により空文字列にできることは，\(S\) が次を満たす部分文字列に分割できることと同値である：A の個数が B の個数の \(2\) 倍であり，左端または右端の文字が B である．

簡単のため，「A の個数が B の個数の \(2\) 倍であり，左端または右端の文字が B である．」という条件を満たす文字列を良い文字列ということにします．

まず必要性を確認しましょう．

消去操作を逆にたどると，空文字列にできるような \(S\) は空文字列に対して AAB または BAA を挿入することを繰り返して得られます．したがって述べられている条件が AAB または BAA の挿入で保たれることを示せばよいです．そのためには，良い文字列に AAB または BAA を挿入したものが良い文字列に分割可能であることを示せばよいです．

挿入が良い文字列のある \(2\) 文字の間に行われた場合には，元々端にあったの文字が挿入後も端にあるのでよいです．そうでない場合つまり良い文字列の先頭または末尾への挿入であった場合には，元の文字列と挿入した \(3\) 文字への分割が良い文字列への分割を与えます．

以上により必要性が示されました．

次に十分性を示します．そのためには良い文字列が操作によって空文字列にできることを示せばよいです．そのためには，長さ \(3\) 以上の良い文字列に対して操作後も良い文字列であるような \(1\) 回の操作を行えることを示せばよいです．

長さ \(3\) の場合には明らかなので，\(S\) が長さ \(6\) 以上の良い文字列であるとします．両端の文字のいずれかは B ですが，左端が B であるとして示せばよいです．\(S\) 内に B が \(n\) 個，A が \(2n\) 個あるとします．

\(S\) の \(1\) 文字目以降を B によって区切ると \(n\) 個の部分に分かれますが，このうちひとつの部分は A を \(2\) 個以上含みます．この部分に対して AAB または BAA を消去する操作を行えば，操作後も先頭の文字が B であるという条件を保ったまま操作を行えることが分かります．以上により十分性も示されました．

---

[3] 解法

結局，動的計画法において次のような遷移を考えればよいことが分かります：

• \(\mathrm{dp}[i+1]\leftarrow \mathrm{dp}[i]+1\)．
• \(i+1, \ldots, j\) 文字目からなる部分文字列が良い文字列であるとき，\(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\)．

後者の計算方法について考えます．

\(S\) の先頭 \(i\) 文字について，A の個数から B の個数の \(2\) 倍を引いた値を \(x_i\) とすると，

• \(x_i=x_j\) かつ \(S\) の \(i+1\) 文字目が B のときに \(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\)．
• \(x_i=x_j\) かつ \(S\) の \(j\) 文字目が B のときに \(\mathrm{dp}[j]\leftarrow \mathrm{dp}[i]\)．

という遷移をできればよいことになります．このためには，各 \(x\) に対して

• \(x_i = x\) であるような \(i\) に対する \(\mathrm{dp}[i]\) の最小値．
• \(x_i = x\) かつ \(S\) の \(i\) 文字目が B であるような \(i\) に対する \(\mathrm{dp}[i]\) の最小値．

を保持するようにすれば，すべての \(\mathrm{dp}[i]\) が全体で \(O(N)\) 時間で計算できます．