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 翻译