AT_arc157_f.[ARC157F] XY Ladder LCS

给定两个由 X 和 Y 组成、长度为 $N$ 的字符串 $S$ 和 $T$。对于每个 $i=1,2,\dots,N$，你可以自由选择是否交换 $S$ 和 $T$ 的第 $i$ 个字符。这样一来，最终可以得到 $2^N$ 种不同的字符串对。请你求出这些字符串对的所有公共子序列（不要求连续）中最长的一个。如果有多个长度相同的公共子序列，请输出其中字典序最小的那个。

公共子序列的定义如下：字符串 $S$ 的子序列是指从 $S$ 中删除 $0$ 个或多个字符后，按原顺序排列剩下的字符所得到的字符串。字符串 $S$ 和 $T$ 的公共子序列是指既是 $S$ 的子序列又是 $T$ 的子序列的字符串。（也可以参考样例 1 的说明。）

输入通过标准输入按以下格式给出。

$N$ $S$ $T$

请输出在所有可能的交换操作后得到的字符串对的公共子序列中，最长且字典序最小的字符串。

限制条件

• $1 \leq N \leq 50$
• $S$ 和 $T$ 均为由 X 和 Y 组成的长度为 $N$ 的字符串。

样例解释 1

• 如果不交换任何字符，XXX 和 YYY 的公共子序列只有空字符串。
• 如果只交换第 1 个字符，YXX 和 XYY 的公共子序列有：空字符串、X、Y。
• 如果只交换第 2 个字符，XYX 和 YXY 的公共子序列有：空字符串、X、Y、XY、YX。
• 如果只交换第 3 个字符，XXY 和 YYX 的公共子序列有：空字符串、X、Y。
• 交换 2 个或更多字符的情况，可以通过交换 $S$ 和 $T$ 本身来等价地考虑上述情况。
• 因此，可能的最长公共子序列为 XY 和 YX，其中字典序最小的是 XY，所以答案为 XY。

样例解释 2

答案也可能是空字符串。

样例解释 3

例如，如果只交换第 2 个字符，可以得到 XYY 作为公共子序列。不存在更长的公共子序列，也不存在长度相同且字典序更小的公共子序列，因此答案为 XYY。

由 ChatGPT 4.1 翻译