Minimum number of swaps to convert a string to palindrome

Question

We are given a string and we have to find out the minimum number of swaps to convert it into a palindrome.

Ex-
Given string: ntiin
Palindrome: nitin
Minimum number of swaps: 1

If it is not possible to convert it into a palindrome, return -1.

I am unable to think of any approach except brute force. We can check on the first and last characters, if they are equal, we check for the smaller substring, and then apply brute force on it. But this will be of a very high complexity, and I feel this question can be solved in another way. Maybe dynamic programming. How to approach it?

Answer 1

First you could check if the string can be converted to a palindrome.

Just have an array of letters (26 chars if all letters are latin lowercase), and count the number of each letter in the input string.

If string length is even, all letters counts should be even.
If string length is odd, all letters counts should be even except one.

This first pass in O(n) will already treat all -1 cases.

If the string length is odd, start by moving the element with odd count to the middle.

Then you can apply following procedure:

Build a weighted graph with the following logic for an input string S of length N:

For every element from index 0 to N/2-1:
- If symmetric element S[N-index-1] is same continue
- If different, create edge between the 2 characters (alphabetic order), or increment weight of an existing one

The idea is that when a weight is even you can do a 'good swap' by forming two pairs in one swap. When weight is odd, you cannot place two pairs in one swap, your swaps need to form a cycle

1. For instance "a    b   a   b"
One edge between a,b of weight 2:
a - b (2)

Return 1

2. For instance: "a     b    c   b    a    c"
a - c (1)
b - a (1)
c - b (1)

See the cycle: a - b, b - c, c - a

After a swap of a,c you get:

a - a (1)
b - c (1)
c - b (1)   

Which is after ignoring first one and merge 2 & 3: 

c - b (2)

Which is even, you get to the result in one swap

Return 2

3. For instance: "a     b    c   a   b   c"
a - c (2)

One swap and you are good

So basically after your graph is generated, add to the result the weight/2 (integer division e.g. 7/3 = 3) of each edge

Plus find the cycles and add to the result length-1 of each cycle

Answer 2

there is the same question as asked! https://www.codechef.com/problems/ENCD12

I got ac for this solution https://www.ideone.com/8wF9DT

//minimum adjacent swaps to make a string to its palindrome
#include<bits/stdc++.h>
using namespace std;
bool check(string s)
{
    int n=s.length();
    map<char,int> m;
    for(auto i:s)
    {
        m[i]++;
    }
    int cnt=0;
    for(auto i=m.begin();i!=m.end();i++)
    {
        if(i->second%2)
        {
            cnt++;
        }
    }
    if(n%2&&cnt==1){return true;}
    if(!(n%2)&&cnt==0){return true;}
    return false;
}

int main()
{
    string a;
    while(cin>>a)
    {
        if(a[0]=='0')
        {
            break;
        }
        string s;s=a;
        int n=s.length();
        //first check if
        int cnt=0;
        bool ini=false;
        if(n%2){ini=true;}
        if(check(s))
        {
            for(int i=0;i<n/2;i++)
            {
                bool fl=false;
                int j=0;
                for(j=n-1-i;j>i;j--)
                {

                    if(s[j]==s[i])
                    {
                        fl=true;
                        for(int k=j;k<n-1-i;k++)
                        {
                            swap(s[k],s[k+1]);
                            cnt++;
//                            cout<<cnt<<endl<<flush;
                        }
//                        cout<<" "<<i<<" "<<cnt<<endl<<flush;
                        break;
                    }
                }
                if(!fl&&ini)
                {
                    for(int k=i;k<n/2;k++)
                    {
                        swap(s[k],s[k+1]);
                        cnt++;

                    }
//                    cout<<cnt<<" "<<i<<" "<<endl<<flush;
                }
            }
            cout<<cnt<<endl;
        }
        else{
            cout<<"Impossible"<<endl;
        }
    }

}

Hope it helps!

Technique behind my code is Greedy first check if palindrome string can exist for the the string and if it can there would be two cases one is when the string length would be odd then only count of one char has be odd and if even then no count should be odd then from index 0 to n/2-1 do the following fix this character and search for this char from n-i-1 to i+1 if found then swap from that position (lets say j) to its new position n-i-1 if the string length is odd then every time you encounter a char with no other occurence shift it to n/2th position..