以下、\(S\) の \(i\) 文字目を \(s_i\) で表します。\(S\) に a が \(c_a\) 個、b が \(c_b\) 個含まれているとします。まず、\(S\) の末尾の文字で場合分けしましょう。

\(S\) の末尾の文字が a のとき

\(k\) を \(s_k=\dots =s_{|S|}=\) a となるような最小の整数とします。また、便宜上 \(s_0=\) b とします。

以下の操作を繰り返すことで \(S\) を bb...b (b が \(c_b\) 個) で始まる文字列にできるので、bb...b (b が \(c_b\) 個) は答えの下界となります。

• \(s_{i-1}=\) b, \(s_i=\) a, \(s_{i+1}=\) a なる \(1\leq i < k\) が存在するなら、\(s_i\) と \(s_k\) に対して操作を行う。
• そうでなく、\(s_{i-1}=\) b, \(s_i=\) a, \(s_{i+1}=\) b なる\(1\leq i < k\) が複数存在するなら、それらから \(2\) つを適当に選んでその間で操作を行う。
• そうでなく、 \(s_i=\) a なる \(i<k\) が存在するなら、\(s_i\) と \(s_k\) に対して操作を行い、終了する。
• そうでないなら、終了する。

証明は、最初 \(2\) つの操作によって \(S\) の末尾が a であるという性質が保たれることと、最初 \(2\) つの操作が不可能なとき\(s_i=\) a なる \(i<k\) は高々 \(1\) 個であることに依ります。

さて、辞書順最大を達成するためには、\(S\) を bb...baa...a (b が \(c_b\) 個、a が \(t\) 個) にできるような最大の \(t\) を求めればよいです。上記の操作がその最大値を達成すること、すなわち操作の回数が最小になることを証明しましょう。末尾に並ぶ a を \(S\) の末端と呼ぶことにします。

末端以外で a が連続する極大な部分、すなわち\(s_{i-1}=\) b, \(s_i=\dots =s_j=\) a, \(s_{j+1}=\) b なる\(1\leq i< j < k\) であって、その長さ \(j-i+1\) が \(1\) のものが \(x\) 個、\(2\) 以上のものが \(y\) 個あるとします。このとき、文字列 \(S\) のポテンシャル \(\phi(S)\) を \(x+2y\) で定義します。

このとき、\(2\) つの a に対するどのような操作も \(\phi(S)\) を \(2\) 以下しか減らさないことが分かります。目的の文字列のポテンシャルは \(0\) なので、少なくとも \(\lceil \phi(S)/2 \rceil\) 回の操作が必要です。また、上記の操作がその最小値を達成することは、\(1,2\) 番目の操作が \(\phi(S)\) を \(2\) 減らすことと \(3\) 番目の操作が高々 \(1\) 回しか行われないことからわかります。

よって、この場合、ポテンシャルの値から解を求めることができます。ポテンシャルの値は線形時間で簡単に求まるので、解も線形時間で求まります。

\(S\) の末尾の文字が b のとき

このとき、b を削除せずに \(S\) の末尾の文字を a にすることは不可能です。\(c_a\) の偶奇と \(S\) の末尾の状態で場合分けします。

\(c_a\) が偶数の時

a ふたつに対して操作を繰り返すことによって \(S\) を bb...b (b が \(c_b\) 個) にでき、このとき \(S\) の末尾に a を持ってくることはできないため、答えは bb...b (b が \(c_b\) 個) になります。

\(c_a\) が奇数かつ \(S\) が ab で終わるとき

最後以外の a ふたつに対する操作を繰り返すことで \(S\) を bb...bab (b が \(c_b-1\) 個、a が \(1\) 個、b が \(1\) 個) にできます。b を削除することでこれより辞書順で大きな文字列を作ることはできず、b を削除せずに a を末尾に持ってくることはできないので、これが作れる辞書順最大の文字列になります。

\(c_a\) が奇数かつ \(S\) が abb で終わるとき

最後以外の a ふたつに対する操作を繰り返すことで \(S\) を bb...babb (b が \(c_b-2\) 個、a が \(1\) 個、b が \(2\) 個) にできます。b を削除することでこれより辞書順で大きな文字列を作ることはできず、b を削除せずに a を末尾から \(2\) 文字以内に持ってくることはできないので、これが作れる辞書順最大の文字列になります。

\(c_a\) が奇数かつ \(S\) が bbb で終わるとき

\(S\) が aa...abb...b (a が \(c_a\) 個、b が \(c_b\) 個) なら、先頭の文字を b にすることはできず、a ふたつに対する操作を繰り返すことで得られる abb...b (a が \(1\) 個、b が \(c_b\) 個) が作れる辞書順最大の文字列になります。

そうでなければ、以下の操作を \(1\) 度だけ行うことによって \(S\) の末尾の文字を a にできます。

• \(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a なる \(1\leq i \leq |S|-2\) が存在するなら、\(s_i\) と \(s_{|S|}\) に対して操作を行う (操作 A)。
• そうでないなら、\(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) b なる \(1\leq i \leq |S|-2\) をとり、\(s_i\) と \(s_{|S|}\) に対して操作を行う (操作 B)。

こうして得られた文字列に \(S\) の末尾の文字が a である場合で述べた操作を行うことで、\(S\) を bb...b (b が \(c_b-2\) 個) で始まる文字列にできます。b を削除せずに \(S\) を先頭に b が \(c_b-2\) 個以上連続する文字列にすることは不可能なので、答えの先頭に連続するb の個数は \(c_b-2\) です。

さて、先ほどと同様、辞書順最大を達成するためには、\(S\) を bb...baa...a (b が \(c_b-2\) 個、a が \(t\) 個) にできるような最大の \(t\) を求めればよいです。上記の操作がその最大値を達成すること、すなわち操作の回数が最小になることを証明しましょう。\(S\) のポテンシャル \(\phi(S)\) を先ほどと同様に定義します。

a を \(S\) の末尾に持ってくるためには、\(S\) の末尾の b に対して操作を行う必要があります。この操作は \(\phi(S)\) を高々 \(2\) しか減少させません。\(c_b-2\) 個の b を残すためには b に対する操作は \(1\) 度しかできないので、a に対するものも含めてどの操作も \(\phi(S)\) を \(2\) 以下しか減らさず、\(\lceil \phi(S)/2 \rceil\) 回の操作が必要なことが分かります。

\(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a なる \(1\leq i \leq |S|-2\) が存在する場合、操作 A によって \(\phi(S)\) は \(2\) 減少するので、上記の方法によって辞書順最大の文字列を作ることができます。

以下、そのような \(i\) が存在しないとします。このとき、操作 B によって \(\phi(S)\) は \(1\) 減少します。よって、もし最初の \(\phi(S)\) が奇数なら、上記の操作によって辞書順最大の文字列を作ることができます。

最初の \(\phi(S)\) が偶数の場合、上記の方法は \(\phi(S)/2+1\) 回の操作を行います。すなわち、\(\phi(S)/2\) 回の操作で \(S\) を bb...baa...a (b が \(c_b-2\) 個、a が \(t\) 個) にできないことを示せばよいです。そのような方法では、どの操作も \(\phi(S)\) を \(2\) 減少させなければならないことに注意しましょう。

さて、\(S\) において、a に対して行うことのできる操作は以下の通りです。先頭に並ぶ a を \(S\) の先端と呼ぶことにします。

• \(S\) の先端の a ふたつに対して操作を行う。\(\phi(S)\) の値は高々 \(1\) しか減少しない。
• \(S\) の先端の a と \(S\) の先端以外の a に対して操作を行う。\(S\) の先端の a が \(2\) 個以下である場合のみ \(\phi(S)\) は \(2\) 減少するが、このとき \(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a なる \(1\leq i\) は新たに発生しない。
• \(S\) の先端以外の a ふたつに対して操作を行う。\(s_{i}=\) b, \(s_{i+1}=\) a, \(s_{i+2}=\) a なる \(1\leq i\) は新たに発生しない。

よって、結局 b に対する操作に際して \(\phi(S)\) を \(2\) 減少させることはできず、\(\phi(S)/2+1\) 回の操作が必要であることが分かります。このことから \(t\) の値を復元できます。\(\phi(S)\) の値は線形時間で求めることができるので、以上をまとめて、線形時間でこの問題を解くことができました。