Let \(X_i\) denote the \(i\)-th character of a \(01\)-sequence \(X\). Additionally, let \(d(X, Y)\) denote the Hamming distance between \(01\)-sequences \(X\) and \(Y\), and \(D := d(S, U) - d(T, U)\). Then, the problem asks to find the lexicographically smallest \(U\) such that \(D = 0\).

• For \(i\) such that \(S_i = T_i\), whether \(U_i\) is \(0\) or \(1\) does not affect \(D\).
• For \(i\) such that \(S_i \neq T_i\), letting \(U_i := S_i\) contributes \(-1\) to \(D\), and \(U_i := T_i\) contributes \(+1\) to \(D\).

Thus, in order to have \(D = 0\), among the indices \(i\) such that \(S_i \neq T_i\), the number of ones such that \(U_i = S_i\) must be equal to those such that \(U_i = T_i\).

This is impossible if the number of indices \(i\) such that \(S_i \neq T_i\), \(d(S, T)\), is odd. If it is even, one should let \(U_i := S_i\) for \(d(S, T)/2\) of those indices, and \(U_i := T_i\) for the remaining \(d(S, T)/2\).

Let us try to find the lexicographically smallest such \(U\).

As stated above, indices \(i\) such that \(S_i = T_i\) contribute nothing to \(D\), so one should let \(U_i := 0\) for them to get the lexicographically smallest.

For indices \(i\) such that \(S_i \neq T_i\), one can use the following greedy strategy.

Scan those indices \(i\) in ascending order. Prioritize assigning \(0\) to \(U_i\) over \(1\) as long as it will not be impossible to end up with \(d(S, T)/2\) indices \(i\) such that \(U_i=S_i\) and \(d(S, T)/2\) such that \(U_i = T_i\).