\(N = |S|\) とし、A を \(+1\)、B を \(-1\) に置き換えて、累積和を取って \(h = (h_0, h_1, \dots, h_N)~(h_0 = 0)\) とします。
\(h\) に残っている添え字の列を \(id = (id_0, id_1, \dots, id_k)\) とします。 (\(k =|h|-1\) としています。）

問題の操作は、\(h\) 内の連続する三項 \((h_a, h_b, h_c)\) であって \(h_a = h_c = h_b-1\) である箇所を選び、\(h_a, h_b\) もしくは \(h_b, h_c\) を削除すると言い換えられます。
文字列が回文となることは、二次元平面上に存在する \(k+1\) 個の点 \((0, h_{id_0}),(1, h_{id_1}), \dots, (k , h_{id_k})\) が点対称であることとなります。
文字列が回文となるために(最終的な) \(h, id\) に含まれる要素を考えます。

まず、操作に関わらず常に \(h_{id_0} = 0\) と \(h_{id_k} = h_N\) が成立します。
従って、点対称の中心は \(\displaystyle \left(\frac{k}{2}, \frac{h_0 + h_N}{2}\right)\) となります。そのため、\((i, h_{id_i})\) に対応する点を \((j, h_{id_j})\) とすると、\(h_{id_i} + h_{id_j} = h_0 + h_N\) が成立しなければなりません。

\(h_x = \min(h)\) であるような \(h_x\) のうち \(1\) つ以上は \(h\) に必ず含まれます。 このとき、\(h_x + h_y = h_0 + h_N\) であるような \(h_y\) も \(h\) に含まれる必要があります。
そのような \(h_y\) が存在しなければ回文を得ることはできません。

\(id\) 内に含まれる \(x, y\) の組を \(1\) つ固定します。（一般性を失わず \(x<y\) とします）
\((h_x, h_{x+1}, \dots, h_y)\) から \(h_x, h_y\) 以外の要素をうまく削除することで、\((h_x, h_x+1, h_x+2, \dots, h_y-1, h_y)\) とできます。

次に \((h_y, h_{y+1}, \dots, h_N)\) に対して \(h_y\) を残したまま操作を行うことを考えます。 \(\displaystyle h_p = \min_{y \leq i \leq N}(h_i)\) とすると、\(h_p\) は \(h\) に必ず含まれ、\(h_p + h_q = h_0 + h_N\) であるような \(h_q~(0 \leq q \leq x)\) も \(h\) に含まれる必要があります。
そのような \(h_q\) が存在しなければ回文を得ることはできません。

\((p, q)\) を \(1\) つ選んで \((x, y) \leftarrow (p,q)\) と更新することを繰り返し、両端まで続けることができれば回文を \(1\) つ得ることができます。

\(x,y\)（および \(p,q\)）として取り得るものが複数存在するときの選び方ですが、\(y,q\) は回文の中心から最も遠いものを選ぶ必要があり、\(x, p\) はどれを選んでもよいです。(証明後述）
ただし、はじめの \(x, y\) のみ \(x < y\) と \(x > y\) の \(2\) 通りを試す必要があります。

ここで \((x, y)\) の更新回数は \(O(\sqrt {|S|})\) 回になります。
これは \(h_{\min(x, y)}\) が、\(\dots \rightarrow -4 \rightarrow 4 \rightarrow -3 \rightarrow 3 \rightarrow -2 \rightarrow 2 \rightarrow -1 \rightarrow 1 \rightarrow 0\) の順に更新されるケースが最悪であることから従います。

\(x, p\) はどれを選んでもよいとしましたが、\(y, q\) と同じく回文中心から最も遠いものを選ぶことにすると Mo’s Algorithm で処理することができます。

最小値取得に Sparse Table などを利用することで \(O(N\sqrt Q + Q\sqrt N + N\log N)\) 時間で解くことができました。

証明集

列 \((a → b)\) を、\(a < b\) なら \((a, a+1, \dots, b)\)、\(a > b\) なら \((a, a-1, \dots, b)\) とする。

• 証明事項 \(1\): \(y~(h_y = h_N - \min(h))\) を \(1\) つ固定したとき、\(h_{x_1} = h_{x_2} = \min(h)\) かつ \(x_1 < x_2 < y\) である \(x_1, x_2\) が存在するならば、\(x_1, x_2\) のうち \(x_2\) を残した方がよい。
  • \(y < x_1 < x_2\) の場合に \(x_1\) を残した方がよいことも同様に示せる。

\(x_1 \in id\) の状態で \(x_1\) 以上 \(y\) 以下に回文の中心があって、\((h_0, \dots, h_{x_1})\) と \((h_{y}, \dots, h_N)\) から \(h_{x_1}\) と \(h_{y}\) 以外の要素をうまく削除して回文にできるとする。
このとき、\(\displaystyle \min_{x_1 \leq i \leq x_2}(h_i) = h_{x_1} = h_{x_2}\) であるため、\(x_2 \in id\) の状態で \(h_{x_1}, \dots, h_{x_2-1}\) を削除でき、これにより先と同じ回文を必ず得ることができる。

(証明事項 \(1\) 了)

• 証明事項 \(2\): \(x~(h_x = \min(h))\) を \(1\) つ固定したとき、\(h_{y_1} = h_{y_2} = h_N - h_x\) かつ \(x < y_1 < y_2\) である \(y_1, y_2\) が存在するならば、\(y_1, y_2\) のうち \(y_2\) を残した方がよい。
  • \(y_1 < y_2 < x\) の場合に \(y_1\) を残した方がよいことも同様に示せる。)
    

\(\displaystyle p = \argmin_{y_1 \leq i \leq y_2}(h_i), q = \argmin_{y_2 \leq i \leq N}(h_i)\) とする。

\((h_0, \dots, h_{x})\) と \((h_{y_1}, \dots, h_N)\) から \(h_x, h_{y_1}\) 以外の要素を削除して長さが最小の回文にできたとする。

\(h_p > h_q\) の場合

\(h_q\) は \(h\) に必ず含まれ、長さ最小のため回文中心付近は \((h_x → h_{y_1} → h_q)\) となる。

このとき、\((h_x, h_{x+1}, \dots, h_{y_2})\) と \((h_{y_2}, h_{y_2+1}, \dots, h_q)\) のそれぞれを \((h_x → h_{y_2}), (h_{y_2} → h_q)\) にできるため同じ回文が得られる。

\(h_p \leq h_q\) の場合

\(h_p\) が \(h\) に含まれることになる。回文のときに \(h_p\) に対応する場所は \(h_{p'}\) とする。

回文になったとき、\((0, \dots, h_{p'} → h_x → h_{y_1} → h_{p}, \dots, last (= h_N))\) の形になっている。 ここで、\(h_p < last\) であるから \(h_{p'} > 0\) である。
\(h\) の隣接項の差は \(1\) なので、接頭に \(h_N- h_q\)、接尾に \(h_q\) に値が等しい要素が存在し、それぞれ (回文中心から最も遠いものを）\(h_l, h_r\) と置くと、\((0, \dots, h_l, \dots, h_{p'} → h_x → h_{y_1} → h_{p}, \dots, h_r, \dots, last)\) と表せる。

\(y_2 < r\) のとき、証明事項 \(1\) より \(q \leq r\) なので \((0, \dots, h_l → h_x → h_{y_2} → h_q, \dots, last)\) と表せる回文が得られる。

\(r < y_2\) のとき、\(\displaystyle h_r = \min_{r \leq i \leq N}(h_i)\) が成立するため \((h_r, h_{r+1}, \dots, h_q)\) から要素を削除して \((h_r)\) を得られることになるが、代わりに \((h_q)\) を得られたことにしてよく、以下 \(y_2 < r\) と同様。

(証明事項 \(2\) 了)

• 証明事項 \(3\): \(y~(h_y = h_N - \min(h))\) を \(1\) つ固定したとき、\(h_{x_1} = h_{x_2} = \min(h)\) かつ \(x_1 < x_2 < y\) である \(x_1, x_2\) が存在するならば、\(x_1, x_2\) のどちらを残してもよい。
  • \(y < x_1 < x_2\) の場合にも \(x_1, x_2\) のどちらを残してもよいことは同様に示せる。

\(x_2\) を残すとする。

\(h_{x_1+1}, h_{x_1+2}, \dots, h_{x_2-1}\) をすべて削除したのならば、\(x_2\) でなく \(x_1\) を残したことにしても変わらない。

\(h_{x_1+1}, h_{x_1+2}, \dots, h_{x_2-1}\) のうち \(h_p~(> h_{x_1})\) を残したとする。 このとき \(h_{x_1}\) を削除できないが、証明事項 \(2\) より \(h_{x_1}\) に対応する点はない。

証明事項 \(1\) と併せると \(x_1, x_2\) のどちらを残してもよいことになる。

(証明事項 \(3\) 了)