题解

思路

在 $S_i=T_i$ 的位置，无论 $U_i$ 取什么，对两个汉明距离的贡献都相同；为使字典序最小应直接取 0。

做法

在 $S_i\ne T_i$ 的位置，若令 $U_i=S_i$，两个距离之差贡献 $-1$，令 $U_i=T_i$ 则贡献 $+1$。因此不同位置的数量必须为偶数，而且其中恰好一半位置选 $S_i$、另一半选 $T_i$。

令这两种选择的剩余额度起初都为不同位置数的一半。从左到右处理不同位置：字符 0 对应的是选 $S_i$ 或选 $T_i$ 中的一种；如果该种额度仍为正，就取 0，否则只能取 1 并消耗另一种额度。这个逐位选择总能保留恰好的剩余额度，并且每一位都选择当前可行的最小字符，所以得到全局字典序最小解。

复杂度

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。