\(i\) 文字目を \(i\) 個「左」にシフトしましょう（文字は A \(\to\) C \(\to\) B \(\to\) A と変化していきます）。すると、操作は「AAA, BBB, CCC のいずれかであるような部分文字列を選び、他のいずれかで置き換える」というものに変化します。

文字列 AAAX（X は任意の文字）を XAAA に変換できることに注意してください（AAAX \(\to\) XXXX \(\to\) XAAA）。

これは、基本的には、任意の三連続する同じ文字を「切除」し、AAA, BBB, CCC から選んだ任意の文字列を任意の位置に挿入することが可能であることを意味します。

以後、文字列 AAA, BBB, CCC を良い文字列と呼びます。

ここで、文字列 \(S\) に対して、操作中に変化しない不変量 \(f(S)\) を次のように定義します。

\(S\) から良い部分文字列を可能な限り切除します（毎回、その前後の部分を連結します）。最終的に残る（良い部分文字列を含まない）文字列が \(f(S)\) です。

\(f(S)\) が well-defined であることは明らかではありません。削除する順番を変えたら、結果が変わってしまうかもしれませんしね。実際は well-defined であることを帰納法により証明します。

長さ \(|S|\) 未満の全ての文字列に対して \(f\) が well-defined であることを仮定します。\(S\) に良い部分文字列が \(1\) 個以下しかなければ、直ちに行える切除のしかたが \(1\) 通り（以下）しかないため、\(f(S)\) は明らかに well-defined です。

\(S\) に \(2\) つの異なる良い部分列があり、これらを削除すると異なる \(f(S)\) が得られるとします。これらが共通部分を持たないとすると矛盾します。なぜなら、\(1\) つ目の部分列を削除した場合、続けて \(2\) つ目を削除することができ、残りの文字列から得られる \(f\) は \(2\) つ目を削除してから \(1\) つ目を削除した場合と同じになるからです。よってこれらは共通部分を持ちますが、するとこの \(2\) つでは同じ文字が連続していることになり、どちらを削除しても全く同じ文字列となります。よって、\(f\) は well-defined です。

続いて、\(S\) を \(T\) に変換可能であることの必要十分条件が \(f(S) = f(T)\) であることを示します。

まず、\(f(S) = f(T)\) であるなら変換可能であることは明らかです。これは、削除した良い文字列をどこにでも入れ直せるためです。

あとは、\(f(S)\) が操作を行うことで変化しないことを示せばよく、これは容易です。良い文字列の削除は任意の順に行ってよいことが分かっているため、操作で変換している良い文字列を削除することもでき、これは \(f(S)\) が変化しないことを意味します。

よって、\(f(S)\) と \(f(T)\) を計算してそれらが同一か確認することで問題を解けます。これは、スタックを使い、文字を一文字ずつ（上述の変換を行ってから）加えていき、末尾三文字が全て一致したときにそれらを削除することで、\(O(N)\) 時間で行えます。