一致させるためには \(A_1=B_1\) が必要です．以下はこれを仮定します．

長さ \(N\) の 01 文字列 \(s\) に対して，長さ \(N-1\) の 01 文字列 \(t\) を \(t_i=s_i\oplus s_{i+1}\) で定めます．

さらに，\(t\) の偶数文字目をすべて反転した文字列を \(u\) とします．

\(s_{i-1}=s_{i+1}\) であるような \(i\) を選んで \(s_i\) を反転させる操作は，以下に対応します．

• \(t_{i-1}=t_i\) であるような \(i\) を選び，\(t_{i-1},t_i\) を flip する
• \(u_{i-1}\neq u_i\) であるような \(i\) を選び，\(u_{i-1},u_i\) を flip する
• \(u\) の連続部分文字列 01 または 10 を選び，swap する

したがって，\(A,B\) に対する \(u\) を \(X, Y\) とすれば，\(X\) を \(Y\) に一致させるためにはそれぞれに含まれる 0 の個数が等しい必要があります． 必要な操作回数の最小値は，\(X,Y\) の 0 の出現位置を \(p,q\) として \(\sum |p_i-q_i|\) です．