To make \(A\) equal to \(B\), it is necessary that \(A_1 = B_1\). We assume this in what follows.

For a binary string \(s\) of length \(N\), define a binary string \(t\) of length \(N-1\) by \(t_i = s_i \oplus s_{i+1}\).

Furthermore, let \(u\) be the string obtained from \(t\) by flipping all even-indexed (second, fourth, …) characters.

The operation of choosing \(i\) such that \(s_{i-1} = s_{i+1}\) and flipping \(s_i\) corresponds to the following:

• Choose \(i\) such that \(t_{i-1} = t_i\), and flip \(t_{i-1}, t_i\)
• Choose \(i\) such that \(u_{i-1} \neq u_i\), and flip \(u_{i-1}, u_i\)
• Choose a contiguous substring 01 or 10 of \(u\), and swap it

Thus, letting \(X\) and \(Y\) be the strings \(u\) corresponding to \(A\) and \(B\), respectively, it is necessary that \(X\) and \(Y\) have the same number of 0s in order for us to make \(X\) equal to \(Y\). The minimum number of operations required is \(\sum |p_i - q_i|\), where \(p\) and \(q\) are the positions of occurrences of 0 in \(X\) and \(Y\), respectively.