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.
Examples:
Input: aabcb
Output: 3
Explanation:
After 1st swap: abacb
After 2nd swap: abcab
After 3rd swap: abcba
Input: adbcdbad
Output: -1
Algorithm
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.
Complexity Analysis
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)
