3 XXX YYY
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.
1 X Y
The answer may be the empty string.
4 XXYX YYYY
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.
{
"problem": {
"name": "XY Ladder LCS",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "AtCoder",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "arc157_f"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
}
]
}