← 返回题目列表

AtCoder · arc157_f

F. XY 梯 LCS

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

给你字符串 S 和 T 长度 N 组成 X 和 Y。 对于每个 i = 1, 2, \dots, N,您可以交换 i- 第一个字符 S 和 i- 第一个字符 T 或选择不这样做。 有 2^N 此过程可能产生的字符串对,包括重复项。找到作为此类对之一的公共子序列(不一定是连续的)的最长字符串。 如果有多个这样的字符串,请找到其中按字典顺序最小的一个。

什么是公共子序列? A 子序列 长度为 $$$m$$$ 的 字符串的 S 是删除零个或多个字符得到的字符串 S 并连接剩余的字符而不改变顺序。 一个 公共子序列 字符串 S 和 T 是一个字符串,它是两者的子序列 S 和 T。 (另请参见示例输出 1。)

约束

  • 1 \leq N \leq 50
  • 每个 S 和 T 是一个长度为的字符串 N 组成 X 和 Y.

输入

输入由标准输入按以下格式给出:

N
S
T

输出

打印最长字符串中按字典顺序排列的最小字符串,该字符串可以是结果字符串对的公共子序列。


示例输入 1

3
XXX
YYY

示例输出 1

XY
  • 如果不交换任何内容,则唯一的公共子序列 XXX 和 YYY 是空字符串。
  • 如果您交换 1-st 字符,公共子序列 YXX 和 XYY 是空字符串, X,和 Y.
  • 如果您交换 2-nd 字符,公共子序列 XYX 和 YXY 是空字符串, X, Y, XY,和 YX.
  • 如果您交换 3-rd 字符,公共子序列 XXY 和 YYX 是空字符串, X 和 Y.

进行两次或多次交换相当于交换后执行上述操作之一 S 和 T 他们自己。 因此,可以作为公共子序列的最长字符串是 XY 和 YX。其中按字典顺序排列较小的, XY,就是答案。


示例输入 2

1
X
Y

示例输出 2


答案可能是空字符串。


示例输入 3

4
XXYX
YYYY

示例输出 3

XYY

XYY 将是一个常见的子序列,例如,仅交换 2-nd 字符。 任何更长或具有相同长度并且按字典顺序更小的字符串在任何交换组合之后都不会成为公共子序列,所以这就是答案。