Given a binary string, that is it contains only 0s and 1s (number of zeros equals the number of ones) We need to make this string a sequence of alternate characters by swapping some of the bits, our goal is to minimize the number swaps.
For example, for the string "00011011" the minimum number of swaps is 2, one way to do it is:
1) swap the bits : 00011011 --->> 00010111
2) swap the bits(after the first swap) : 00010111 --->> 01010101
Note that if we are given the string "00101011" we can turn it into an alternate string starting with 0(that requires 3 swaps) and also into alternate string starting with 1.( that requires one swap - the first and the last bits ).
So the minimum in this case is one swap.
What is the most efficient way to solve it?