F - XY Ladder LCS Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

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

共通部分列とは 文字列 S の部分列とは，S から 0 個以上の文字を削除して，残った文字を元の順で並べて得られる文字列のことをいいます． 文字列 S, T の共通部分列とは，S と T のどちらの部分列でもあるような文字列のことをいいます． （出力例 1 の説明も参考にしてください．）

制約

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

入力

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

N
S
T

出力

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

入力例 1

3
XXX
YYY

出力例 1

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 が答えとなります．

入力例 2

1
X
Y

出力例 2



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













入力例 3
4
XXYX
YYYY












出力例 3
XYY



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






Score : 900 points







Problem Statement
You are given strings S and T of length N consisting of X and Y.
For each i = 1, 2, \dots, N, you can swap the i-th character of S and the i-th character of T or choose not to do it.
There are 2^N pairs of strings that can result from this process, including duplicates. Find the longest string that is a common subsequence (not necessarily contiguous) of one of such pairs.
If there are multiple such strings, find the lexicographically smallest of them.



What is a common subsequence?
A subsequence of string S is a string obtained by deleting zero or more characters from S and concatenating the remaining characters without changing the order.
A common subsequence of strings S and T is a string that is a subsequence of both S and T.
(See also Sample Output 1.)













Constraints
    

  • 1 \leq N \leq 50
    • 

  • Each of S and T is a string of length N consisting of X and Y.
    • 
















Input
The input is given from Standard Input in the following format:


N
S
T












Output
Print the lexicographically smallest of the longest strings that can be a common subsequence of the resulting pair of strings.















Sample Input 1
3
XXX
YYY












Sample Output 1
XY



    

  • If you swap nothing, the only common subsequence of XXX and YYY is the empty string.
    • 

  • If you swap the 1-st characters, the common subsequences of YXX and XYY are the empty string, X, and Y.
    • 

  • If you swap the 2-nd characters, the common subsequences of XYX and YXY are the empty string, X, Y, XY, and YX.
    • 

  • If you swap the 3-rd characters, the common subsequences of XXY and YYX are the empty string, X and Y.
    • 



Doing two or more swaps is equivalent to one of the above after swapping S and T themselves.
Thus, the longest strings that can be a common subsequence are XY and YX. The lexicographically smaller of them, XY, is the answer.













Sample Input 2
1
X
Y












Sample Output 2


The answer may be the empty string.













Sample Input 3
4
XXYX
YYYY












Sample Output 3
XYY



XYY will be a common subsequence after, for instance, swapping just the 2-nd characters.
Any string that is longer or has the same length and is lexicographically smaller will not be a common subsequence after any combination of swaps, so this is the answer.