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$.
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.
010100. There are 4 zeros here. So we get
Now, we insert the 1 in
001100 into it. And we get
Then we insert the 1 in
010100 into it. And we get