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.
Code:
