01文字列の隣接swapは 1 を動かす操作と考えられる。よって、\(\operatorname{dist}(S,T)\) は 1 の移動距離の総和として言い換えられ、定式化すると以下のようになる。

• 良い文字列 \(S\) における 1 の位置を \(p_1 \lt p_2 \lt \ldots \lt p_N\)
• 良い文字列 \(T\) における 1 の位置を\(q_1 \lt q_2 \lt \ldots \lt q_N\)

として、

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

例えば \(\operatorname{dist}(100110,001011)\) は、\(p = (1, 4, 5)\)、 \(q = (3, 5, 6)\) なので \(\operatorname{dist} = |1 - 3| + |4 - 5| + |5 - 6| = 4\)、といった具合である。

この言い換えにより、

• 良い文字列 \(A\) における 1 の位置を\(a_i\)
• 良い文字列 \(B\) における 1 の位置を\(b_i\)
• 良い文字列 \(C\) における 1 の位置を\(c_i\)

としたときに、\(X\) を

• \(X\) の \(i\) 番目の 1 の位置 \(x_i\) を、\(a_i, b_i, c_i\) の中央値とする

と構成するのが最適であることがわかる。(厳密には、この構成した \(X\) が必ず良い文字列、つまり \(x_i\) が狭義単調増加であることを言う必要がある)。

例えばサンプル

2
1100
1010
0011

ならば、

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

なので、

• \(x_1\) は \((1, 1, 3)\) の中央値の \(1\)、
• \(x_2\) は \((2, 3, 4)\) の中央値の \(3\)

として \(X = 1010\) が得られる。

また、最適な \(X\) は実は一意であることもわかる。