Minimum number of swaps required to make a binary string palindrome

Question

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.

Answer 1

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 an 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 size of 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.

Answer 2

You got the most cleaver answer already on the swaps count. That solve the problem you stated already. If you are interested in using the approach to build up a palindromized string too, than some extra steps need to be added. You need not only to count the swaps but also to keep memory of where they need to happen and what is the best approach to get them done. Here you can find an extension of the solution in Java. The first method only counts (basically the Java implementation of the algorithm above) the second performs the swaps too. On an average count made on randomly generated strings from 1 to 10000 character long, I noticed the execution time deteriorates by 50% due to the swaps overhead. I'm sure it can be improved more.

private static int countOnly(String input)
{
    int n = input.length();
    int count = 0;
    char[] inputAsCharArray = input.toCharArray();
    for (int i = 0; i < n / 2; i++)
    {
        if (inputAsCharArray[i] != inputAsCharArray[n - i - 1])
        {
            count++;
        }
    }
    if (count % 2 == 1 && n % 2 == 0)
        return -1;      
    return (count + 1) / 2;
}
private static int countAndPalindromize(String input)
{
    int n = input.length();
    int swapsCount = 0;
    int swaps[] = new int[n/2];
    for(int i = 0; i < swaps.length; i++)
    {
        swaps[i] = -1;
    }
    char[] inputAsCharArray = input.toCharArray();
    int count = 0;
    for (int i = 0; i < n / 2; i++)
    {
        if (inputAsCharArray[i] != inputAsCharArray[n - i - 1])
        {
            count++;
            if (swaps[0] != -1)
            {
                if (inputAsCharArray[i] != inputAsCharArray[swaps[0]])
                {
                    char c = inputAsCharArray[i];
                    inputAsCharArray[i] = inputAsCharArray[swaps[0]];
                    inputAsCharArray[swaps[0]] = c;
                    for (int y = 1; y <= swapsCount; y++)
                    {
                        swaps[y - 1] = swaps[y];
                    }
                    swapsCount--;
                }
                else if (inputAsCharArray[n - i - 1] != inputAsCharArray[swaps[0]])
                {
                    char c = inputAsCharArray[n - i - 1];
                    inputAsCharArray[n - i - 1] = inputAsCharArray[swaps[0]];
                    inputAsCharArray[swaps[0]] = c;
                    for (int y = 1; y <= swapsCount; y++)
                    {
                        swaps[y - 1] = swaps[y];
                    }
                    swapsCount--;
                }
                else
                {
                    swaps[swapsCount++] = n - i - 1;
                }
            }
            else
            {
                swaps[swapsCount++] = n - i - 1;
            }
        }
    }
    
    if (count % 2 == 1 && n % 2 == 0)
        return -1;
    return (count + 1) / 2;
}