Minimum number of swaps required to make a binary string palindrome-CodePudding

Give a binary string consisting of 0's and 1's only. E.g., 0100101. We are allowed to pick
any two indexes and swap them. We have to return the minimum number of swaps required to make
it a palindrome or -1 if it cannot. The string 0100101 can be made a palindrome by swapping
(3,4)-> 0101001 and swapping (0,1) -> 1001001 which is a palindrome. In this case, the
correct answer is 2.

My Thoughts:
I thought it over and tried to find out some properties. But, like we need to swap either 1,0 or 0,1, swapping the indexes with the same values doesn't make sense.
If the string is of even length, then the number of 0's and 1's must be equal, and if it
is of odd length, then one of the numbers of 1's and o's is odd, and the other is even.
If this condition is not satisfied, then it is not possible to make the string a palindrome
But whether this is a sufficient condition or not, I am not sure.

CodePudding user response：

You could compare the outermost two digits: if they are the same, nothing needs to happen, nor should these digits ever be involved in a swap.

If they are different, take note of that, and don't swap anything yet.

Continue with the second digit at each end. Compare them. If they are different, and this is the second time we have a difference, note how we can solve those two differences with one swap. An example:

 10.......10

With one swap this can become:

 10.......01

So we can resolve two differences with one swap. This means that if we find and even number of differences -- as we walk along the binary string from the two ends inwards -- there is a solution, and it takes half that number of swaps.

If the number of differences is odd, there is still a solution if the input string is odd, because then that middle digit can be swapped with a digit from that last difference, and so get a palindrome.

There is however no solution when the number of differences (in this algorithm) is odd and the number of digits in the input is even.

Now, you don't actually have to perform the swaps, as the challenge only asks for the number of swaps.

This leads to the following code:

def numswaps(binary):
    n = len(binary)
    count = 0 
    for i in range(n // 2):
        if binary[i] != binary[n - i - 1]:
            count  = 1
    if count % 2 == 1 and n % 2 == 0:
        return -1
    return (count   1) // 2

Your thoughts

If the string is of even length, then the number of 0's and 1's must be equal,

No, if the string is of even length, then the number of 0's must be even (and this implies the number of 1's is even).

and if it is of odd length, then one of the numbers of 1's and o's is odd, and the other is even.

This is a tautology: it is always true. It is impossible to have a string of odd length where the number of 1's and 0's is not like you state. There is always a solution for an odd length string.