\(N\) 個の A と \(N\) 個の B からなり同じ文字が隣り合う箇所がない文字列は ABABAB..., BABABA... の \(2\) 種類しかありません。よって「 \(S\) を \(T\) にするには何回の操作が必要か？」というタイプの問題を \(2\) 回解けば元の問題に答えることができます。

同じ文字が隣り合っている箇所に対して操作をする意味はありません。よって、操作の前後で A の順序が入れ替わることはありません。つまり、 \(S\) の前から \(k\) 番目にある A は、 \(T\) の前から \(k\) 番目にある Aの位置に移動します。

\(S\) のうち前から \(k\) 番目にある A の位置を \(X_k\) 、 \(T\) のうち前から \(k\) 番目にある A の位置を \(Y_k\) とします。\(1\) 回の操作では \(1\) 個の A の位置がちょうど \(1\) 変化するため、\(S\) を \(T\) にするには最低でも \(\sum_k |X_k-Y_k|\) 回の操作が必要です。

逆に、次のように操作することで、操作ごとに \(\sum_k |X_k-Y_k|\) が \(1\) 減少するためその最小回数を達成できます。

• 以下の操作を、\(S\) が \(T\) に一致するまで繰り返す
  • \(X_k<Y_k\) であるような \(k\) について、\(k\) の降順に \(X_k\) 文字目と \(X_k+1\) 文字目を入れ替える
  • \(X_k>Y_k\) であるような \(k\) について、\(k\) の昇順に \(X_k\) 文字目と \(X_k-1\) 文字目を入れ替える

この問題では \(T\) として考慮する必要があるのは ABABAB... と BABABA... であり、これはそれぞれ \(Y=(1,3,5,\ldots),(2,4,6,\ldots)\) に対応するため求める答えは \(\min\{\sum_k|X_k-(2k-1)|, \sum_k|X_k-2k|\}\) となります。\(X_k\) は \(O(N)\) で求めることができるため、この問題は \(O(N)\) で解けます。