Hints

Hint 1

Can you construct such binary string of length $2N$?

Answer to Hint 1

String of $2N$ zeros works.

Hint 2

Can you solve the problem for $2$ strings?

Hint 3

Why does the problem ask for exactly $3$ strings, not $2$?

Hint 4

There exists some string of length $2N+1$ which is a subsequence of any string $S + S$, where $S$ is any string of length $2N$ containing exactly $N$ zeros and $N$ ones. What can this string look like?

Hint 5

$0\cdot N + 1\cdot N + 0$ works. Why?

Solution

For any binary string $S$ of $N$ zeros and ones, $S+S$ contains as a subsequence string $0\cdot N + 1\cdot N + 0$.

Proof

Let the positions of zeros in string $S$ be $a_1, a_2, \dots, a_N$. Then the positions of zeros in string $S+S$ are:
$a_1, a_2, \dots, a_N, a_1, + 2N, a_2 + 2N, \dots, a_N + 2N$.

So, the distance between the $N$-th zero and the $2N$-th is exactly $2N$, which means that there are exactly $N$ ones between them.

Total asymptotics $O(N)$.

Extra comments

This is not the only solution: similarly to above, for any \(1\le A, B\le N\) with \(A+B = N+1\), \(0\cdot A + 1\cdot N + 0\cdot B\) suffices (and \(1\cdot A + 0\cdot N + 1\cdot B\) ).

There constraint of \(2N+1\) is tight: it can be proved that strings \(0 \cdot N + 1 \cdot N + 0 \cdot N + 1 \cdot N\) and \((01)\cdot (2N)\) don’t have a common subsequence of length \(2N+2\).