Binary Literature
Contest: Codeforces Round 715 (Div. 1)
Difficulty rating: 1900
Tags: constructive algorithms, greedy, implementation, strings, two pointers

A bitstring is a string that contains only the characters 0 and 1.

Koyomi Kanou is working hard towards her dream of becoming a writer. To practice, she decided to participate in the Binary Novel Writing Contest. The writing prompt for the contest consists of three bitstrings of length $$$2n$$$. A valid novel for the contest is a bitstring of length at most $$$3n$$$ that contains at least two of the three given strings as subsequences.

Koyomi has just received the three prompt strings from the contest organizers. Help her write a valid novel for the contest.

A string $$$a$$$ is a subsequence of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero) characters.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

Each of the following three lines contains a bitstring of length $$$2n$$$. It is guaranteed that these three strings are pairwise distinct.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print a single line containing a bitstring of length at most $$$3n$$$ that has at least two of the given bitstrings as subsequences.

It can be proven that under the constraints of the problem, such a bitstring always exists.

If there are multiple possible answers, you may output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the bitstrings 00 and 01 are subsequences of the output string: 010 and 010. Note that 11 is not a subsequence of the output string, but this is not required.

In the second test case all three input strings are subsequences of the output string: 011001010, 011001010 and 011001010.

Example input:
2
1
00
11
01
3
011001
111010
010001

Example output:
010
011001010

Editorial:
First solution
Let's focus on two bitstrings $$$s$$$ and $$$t$$$. How can we get a short string that has them both as subsequences? Well, suppose both strings have a common subsequence of length $$$L$$$. Then we can include this subsequence as part of our string. Then we just place the remaining characters of both sequences in the correct positions between the characters of this common sequence, to make both strings a subsequence of the result. This saves us $$$L$$$ characters compared to just concatenating $$$s$$$ and $$$t$$$ since the characters of the common subsequence only have to included once, i.e. this uses $$$|s| + |t| - L$$$ characters.
Now, in our problem, all strings have a length of $$$2n$$$, so this algorithm will use a total of $$$4n - L$$$ characters. This means if we can find two strings that have a common subsequence of length $$$n$$$, we can finish the problem. However, the usual algorithm for computing the longest common subsequence works in $$$\mathcal{O}(n^2)$$$, which is unlikely to pass the time limit, so we have to construct this common subsequence more concretely.
The observation is that because each character is either $$$0$$$ or $$$1$$$, one of these characters must appear at least $$$n$$$ times. Call such a character frequent. Now since each string has at least one frequent character, two of these frequent characters are equal. Considering these two strings and their frequent character we find a common subsequence of length $$$n$$$, equal to either $$$000\dots 0$$$ or $$$111\dots 1$$$.
Second solution
This solution uses a similar idea, in a way that is a bit easier to implement. Consider three pointers $$$p_1, p_2, p_3$$$, pointing to a character in each string, and a string $$$t$$$ representing our answer. These pointers will represent the prefixes of each string that we have represented in our answer. Initially, $$$t$$$ is empty and $$$p_1 = p_2 = p_3 = 1$$$ (here our strings are $$$1$$$-indexed).
Now we will add characters to $$$t$$$ one by one. At each step, consider the three characters pointed at by our three pointers. Since they are either $$$0$$$ or $$$1$$$, two of them are equal. Add this equal character to $$$t$$$, and advance the pointers that match this character by $$$1$$$.
Continue this algorithm until one of the strings is completely contained in $$$t$$$, let's say $$$s_1$$$. At this point, suppose $$$t$$$ has $$$k$$$ characters, and thus the pointers have advanced by at least $$$2k$$$, since at least two of them advance on each step. We have exhausted the characters of $$$s_1$$$, so we have advanced $$$p_1$$$ by $$$2n$$$, and the other two pointers have advanced $$$2k - 2n$$$, and thus one of them has advanced by at least $$$k - n$$$. Now just add the remaining characters of this string to $$$t$$$. There are at most $$$2n - (k - n) = 3n - k$$$ of them, so in the end $$$t$$$ has at most $$$3n$$$ characters.