## Solutions:

It is very simple to prove that the string which length is $3n$ can be obtained.

Let's get two string which length is $2n$, one is `000000`

, another one is `111111`

. So we can find that: when we are building the third one. The maximum difference between the first two strings is $n$.

For example `001111`

, the maximum difference between first two is: $max(2,4)=4$. Which is more than $n$. And `000111`

is 3.

So the length of the common part is more than $n$. For the different part (which length is lesser than $n$), only need insert into the common part.

Base on this proof. We need to find the longest common subsequence of two strings. Can do it, but too complex. Because it's bitstring.

So for any bitstring, Either the number of 0s is large, or the number of 1s is large.

Let's consider there are more 0s in the string. As mentioned before. Only need to insert 1 into the 0s.

For example, `001100`

and `010100`

. There are 4 zeros here. So we get `0000`

.

Now, we insert the 1 in `001100`

into it. And we get `001100`

.

Then we insert the 1 in `010100`

into it. And we get ** 01011100**.