{"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 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.\nWhat 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.)\n\n## Constraints\n\n*   $1 \\leq N \\leq 50$\n*   Each of $S$ and $T$ is a string of length $N$ consisting of `X` and `Y`.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S$\n$T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc157_f","tags":[],"sample_group":[["3\nXXX\nYYY","XY\n\n*   If you swap nothing, the only common subsequence of `XXX` and `YYY` is the empty string.\n*   If you swap the $1$\\-st characters, the common subsequences of `YXX` and `XYY` are the empty string, `X`, and `Y`.\n*   If you swap the $2$\\-nd characters, the common subsequences of `XYX` and `YXY` are the empty string, `X`, `Y`, `XY`, and `YX`.\n*   If you swap the $3$\\-rd characters, the common subsequences of `XXY` and `YYX` are the empty string, `X` and `Y`.\n\nDoing 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\nX\nY","The answer may be the empty string."],["4\nXXYX\nYYYY","XYY\n\n`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."]],"created_at":"2026-03-03 11:01:14"}}