AT_arc157_f [ARC157F] XY Ladder LCS

[problemUrl]: https://atcoder.jp/contests/arc157/tasks/arc157_f `X`, `Y` からなる長さ $ N $ の文字列 $ S,\ T $ が与えられます． 各 $ i\ =\ 1,\ 2,\ \dots,\ N $ に関して，$ S $ の $ i $ 文字目と $ 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 $ の文字列である． ### Sample Explanation 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` が答えとなります． ### Sample Explanation 2 答えが空文字列となることもあります． ### Sample Explanation 3 たとえば $ 2 $ 文字目だけを入れ替えた場合に `XYY` が共通部分列となります． より長い文字列，あるいは，同じ長さであって辞書順でより早く現れる文字列は，どのように入れ替えたとしても共通部分列にはなり得ないため，これが答えとなります．