\(01\) 列 \(X\) の \(i\) 文字目を \(X_i\) で表します。 また、\(01\) 列 \(X, Y\) のハミング距離を \(d(X, Y)\) で表し、\(D := d(S, U) - d(T, U)\) と定めます。 このとき、本問題は \(D = 0\) を満たす \(U\) のうち辞書順最小のものを求める問題です。

• \(S_i = T_i\) を満たす \(i\) については、\(U_i\) を \(0, 1\) のどちらにしても \(D\) に変化を与えません。
• \(S_i \neq T_i\) を満たす \(i\) については、\(U_i := S_i\) とすれば \(-1\) だけ、\(U_i := T_i\) とすれば \(+1\) だけ、 \(D\) に寄与します。

よって、\(D = 0\) であるには、\(S_i \neq T_i\) を満たす \(i\) のうち \(S_i\) に一致するものと \(T_i\) に一致するものの個数が等しくなければなりません。

\(S_i \neq T_i\) を満たす \(i\) の個数 \(d(S, T)\) が、 奇数のときはこれは不可能であり、偶数のときはそのうち \(d(S, T)/2\) 個では \(U_i := S_i\) とし、残りの \(d(S, T)/2\) 個では \(U_i := T_i\) とすれば良いです。

そのような \(U\) のうち辞書順最小のものを求めることを考えます。

\(S_i = T_i\) を満たす \(i\) は、上述の通り \(D\) に寄与しないため、辞書順最小を求める上では \(U_i := 0\) として良いです。

\(S_i \neq T_i\) を満たす \(i\) については、

小さい \(i\) から順に走査していき「最終的に、 \(U_i=S_i\) であるものと \(U_i = T_i\) であるものが \(d(S, T)/2\) 個ずつになる」という目標が達成できなくならない限り、\(U_i\) に \(1\) より \(0\) を優先的に割り当てていく

という貪欲なアルゴリズムで決定することができます。