C は変化しないので，A,B が連続する部分に注目します．

A の重みを \(2\)，B の重みを \(1\) とすると，操作によって重みの和は変化しません． 今，A,B が連続する部分の重みの和が \(W\) だとします．

この時，以下のように変化させるのが最適です．

• \(W\) が偶数のケース：A が \(W/2\) 個並んだ文字列にする．
• \(W\) が奇数のケース：A が \((W-1)/2\) 個，それに続いて B が \(1\) 個並んだ文字列にする．

これが重み一定の下で辞書順最小であることはすぐにわかります． また，実際にこれを達成する操作も可能です．（すべての A を一旦 B に変えた後，先頭から順番に A にしていけばよい．）

計算量は \(O(N)\) です．

解答例(c++)