配点 : $900$ 点

問題文

X, Y からなる長さ $N$ の文字列 $S, T$ が与えられます． 各 $i = 1, 2, \dots, N$ に関して，$S$ の $i$ 文字目と $T$ の $i$ 文字目を入れ替えるかどうかを自由に選べます． このとき，結果として得られる文字列の組はのべ $2^N$ 通りありますが，そのいずれかの共通部分列（連続とは限らない）となる文字列のうち最長のものを求めてください． ただし，そのような文字列が複数ある場合，そのうち辞書順で最初に現れるものを求めてください．

制約

• $1 \leq N \leq 50$
• $S, T$ はそれぞれ X, Y からなる長さ $N$ の文字列である．

入力

入力は以下の形式で標準入力から与えられる．

$N$

$S$

$T$

出力

入れ替え後の文字列の組の共通部分列としてあり得る最長の文字列のうち，辞書順で最初に現れるものを出力せよ．

3
XXX
YYY

XY

• どの文字も入れ替えない場合，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 が答えとなります．

1
X
Y

答えが空文字列となることもあります．

4
XXYX
YYYY

XYY

たとえば $2$ 文字目だけを入れ替えた場合に XYY が共通部分列となります． より長い文字列，あるいは，同じ長さであって辞書順でより早く現れる文字列は，どのように入れ替えたとしても共通部分列にはなり得ないため，これが答えとなります．