まず、\(A, B, C\) を \(0, 1, 2\) に変換します。

そして、長さ \(N\) の任意の良い文字列 \(S\) を、以下の条件を満たす長さ \(N\) の数列 \(A\) で表します。

• $1 \le i \le n-1$ に対して $|A_{i+1} - A_i| = 1$
• $A_i \equiv S_i \bmod 3$

このような数列も良いと呼ぶことにします。

\(A_1\) の値を選ぶと、このような数列 \(A\) は一意に定まることが簡単に分かります。

これで、行える操作は、「\(A\) が良い数列のままであるように \(i\) を選んで \(A_i\) を \(A_i \pm 2\) に変える」となります。

では、\(2\) つの良い数列 \(A_1, \dots, A_N\) と \(B_1, \dots, B_N\) を考えましょう。前者から後者を得るために必要な最小の操作回数はいくつでしょうか？

もし \(A_1 \bmod 2 \neq B_1 \bmod 2\) であるなら、これは明らかに不可能です。

そうでなければ、この回数が \(\sum_{i = 1}^N \frac{|A_i - B_i|}{2}\) であることが証明できます。

明らかに、少なくともこの回数の操作が必要です。したがって、この回数で十分であることを示せば十分です。このためには、任意の \(2\) つの異なる数列であって \(A_1 \equiv B_1 \bmod 2\) であるようなものについて、\(\sum_{i = 1}^N |A_i - B_i|\) を \(2\) 減らすような操作が可能であることを示せば十分です。

そうでないと仮定します。\(A_i>B_i\) であるような \(i\) が存在するとします（\(A_i < B_i\) であるような \(i\) が存在する場合も同様）。\(A_i > B_i\) であるような \(i\) のうち、\(A_i\) が最大のものを考えます。この \(A_i\) を \(2\) 減らしても数列は良いままであることを示します。

このためには、\(A_i\) に隣接する要素が存在するなら、それらは全て \(A_i - 1\) に等しいことを示す必要があります。そうでないと仮定すると、（一般性を失うことなく）\(A_{i+1} = A_i + 1\) といえます。すると \(A_{i+1} = A_i + 1 > B_i + 1 \ge B_{i+1}\) となってしまい、\(i\) の選び方と矛盾します。

これを示せれば、あとは簡単です。\(B_1 \equiv A_1 \bmod 2\) かつ \(B_1 \equiv T_1 \bmod 3\) であるような \(B_1\) の値の選択肢全てに対する \(\sum_{i = 1}^N |A_i - B_i|\) のうち最小のものを求めればよく、これは \(O(n)\) 時間で行えます。