公式解説より計算量は悪化しますが、英小文字 \(2\) つの組を頂点、そこから文字を追加した時の美しさの変化を辺としたグラフ上でワーシャルフロイド法をすると、ワードサイズを \(\sigma=26\) として計算量が \(O(\sigma^6)\) となり、C++などの高速な言語であればかろうじて間に合います。

この方法の場合、文字列が \(1\) 文字または \(2\) 文字の場合の処理に注意してください。

実装例(C++23,247ms)