Adjacent swaps of a 01 string can be thought of as the operation of moving a 1. Thus, \(\operatorname{dist}(S,T)\) can be restated as the total moving distance of the 1s, which can be formulated as follows.

Let the positions of 1s in the good string \(S\) be \(p_1 \lt p_2 \lt \ldots \lt p_N\), and let the positions of 1s in the good string \(T\) be \(q_1 \lt q_2 \lt \ldots \lt q_N\). Then,

\[ \operatorname{dist}(S,T)=\sum_{i=1}^{N}|p_i-q_i|. \]

For example, \(\operatorname{dist}(100110,001011)\) is computed as follows: since \(p = (1, 4, 5)\) and \(q = (3, 5, 6)\), we get \(\operatorname{dist} = |1 - 3| + |4 - 5| + |5 - 6| = 4\).

Using this restatement, let the positions of 1 in the good strings \(A, B, C\) be \(a_i\), \(b_i\), \(c_i\), respectively. Then we can see that it is optimal to construct \(X\) as follows:

• Let the position \(x_i\) of the \(i\)-th 1 of \(X\) be the median of \(a_i, b_i, c_i\).

(To be precise, it needs to be shown that the constructed \(X\) is always a good string, that is, \(x_i\) is strictly increasing.)

For instance, for the sample

2
1100
1010
0011

we have

• \(a = (1, 2)\)
• \(b = (1, 3)\)
• \(c = (3, 4)\)

so

• \(x_1\) is \(1\), the median of \((1, 1, 3)\),
• \(x_2\) is \(3\), the median of \((2, 3, 4)\),

giving \(X = 1010\).

It also turns out that the optimal \(X\) is in fact unique.