Count minimum swap to make string palindrome
Given a string s, the task is to find out the minimum no of adjacent swaps required to make string s palindrome. If it is not possible, then return -1.
After 1st swap: abacb
After 2nd swap: abcab
After 3rd swap: abcba
The following are detailed steps to solve this problem.
- Take two-pointer where the first pointer track from the left side of a string and second pointer keep track from the right side of a string.
- Till the time we find the same character, keep moving the right pointer to one step left.
- If the same character not found then return -1.
- If the same character found then swap the right pointer’s character towards the right until it is not placed at its correct position in a string.
- Increase left pointer and repeat step 2.
Time Complexity: Since we are running two nested loops on the length of string, the time complexity is O(n2)
Auxiliary Space: Since we aren’t using any extra space, Therefore Auxiliary space used is O(1)