同じ文字が \(2\) つ以上連続する部分をブロックと呼ぶことにします。ブロックは、\(S\) の最初のブロックであるか、ひとつ前に現れたブロックと異なる文字からなるブロックであるとき、本質的であると呼ぶことにします。例えば、文字列 abbbcbbccca には、\(2,3,4\) 文字目の b からなるものと \(8,9,10\) 文字目の c からなるものの \(2\) つの本質的なブロックがあります。\(6,7\) 文字目の b からなるブロックは、ひとつ前に b からなるブロックが存在するため、本質的ではありません。

さて、以下のような操作列を考えます。本質的なブロック \(B\) に対し、その先頭と末尾の文字をそれぞれ \(l(B)\) 文字目と \(r(B)\) 文字目と書くことにしましょう。

• 本質的なブロック \(B\) であって、\(r(B)\neq |S|\) なるものが存在しないなら、終了する。
• 存在するなら、\(S\) の \(r(B)-1, r(B), r(B)+1\) 文字目を用いて操作を行う。

この操作列が操作回数の最大値を達成することを証明しましょう。各本質的なブロック \(B\) に対し、そのポテンシャル \(\phi(B)\) を以下の合計で定義します。\(B\) の次に現れる本質的なブロックを \(B'\) としましょう。

• \(r(B)+1,\dots, l(B')-1\) 文字目からなる列に含まれる、\(B\) の文字と異なる文字の個数
• \(l(B'),\dots, |S|\) 文字目からなる列の文字数 \(|S|-l(B')+1\)

文字列 \(S\) のポテンシャル \(\phi(S)\) を、各本質的なブロック \(B\) に対する \(\phi(B)\) の合計と定義します。

さて、定義より、どのような操作も \(\phi(S)\) を \(1\) 以上減少させることが分かります。逆に、上記の操作列のどの操作でも \(\phi(S)\) はちょうど \(1\) 減少し、終了時には \(\phi(S)=0\) であることもわかります。よって、上記の操作列は操作回数の最大値 \(\phi(S)\) を達成します。\(\phi(S)\) は線形時間で求めることができるので、この問題を線形時間で解くことができます。