# Min Swaps to Make Palindrome Solution

Page Contents

This question can be called as “Minimum Adjacent Swaps to Make Palindrome” or “Min Swaps to Make Palindrome” either way both are same. Make sure you look through the code before copying it.

## Microsoft Online Assessment Min Swaps to Make Palindrome

A palindrome is a string of letters that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of times you need to swap to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string “mamad” may be transformed into the palindrome “madam” with 3 swaps:

Also See: Microsoft Online Assessment Questions and Solution

### Input

The Input will have number of test cases. For each test case, one line of input containing a string of up to 100 lowercase letters will be there. Terminate the input with a 0(zero).

### Output

Output consists of one line. This line will contain the number of swaps, or “Impossible” if it is not possible to transform the input string to a palindrome.

### Example

```Input:
asflkj
aabb
0```
```Output:
3
Impossible
2```

## Solution

Program Python:

```def is_permutation_of_palindrome(s):
s = s.lower()
bit_vector = 0 << 25

for char in s:
index = ord(char) - 97
bit_vector = (1 << index) ^ bit_vector

return (bit_vector - 1) & bit_vector == 0

def solution(s):
if is_permutation_of_palindrome(s):
s = list(s)
i, j = 0, len(s) - 1
total_swaps = 0

while j > i:
k = j
while k > i and s[i] != s[k]:
k -= 1

while k < j:
if s[i] == s[j]:
break
s[k], s[k + 1] = s[k + 1], s[k]
total_swaps += 1
k += 1

i += 1
j -= 1

else:
//Based on the question you can either return -1 or Impossible.
return "Impossible"

while True:
s=input().strip()
if s=='0':
break
print(solution(s))```

Program Java:

Algorithm:
1. First check the given string is a jumbled/shuffled palindrome or not.
2. Next have two pointers p1 at 0 and p2 at s.length – 1 and start iterating.
3. If chars at both the pointers are same then just shrink the window (increase the p1 and decrease the p2).
4. or Else
a. find the matching pair and swap the char to p2 index (increase swap count while swapping) and finally shrink the window.
b. if not found just swap once with adjacent index and increase the swap count (do not shrink the window here)
5. Print the Swap Count

Time Complexity: O(n) to find Palindrome + [ O(n) for two pointer iteration * O(n) for checking and swapping ] so => O(n^2)
Space Complexity: O(n)

```private int getNoOfSwaps(String s) {
if(s == null || s.length() == 0) return -1;
int totalSwaps = 0;

if(isShuffledPalindrome(s)) {
char[] chars = s.toCharArray();
int p1 = 0, p2 = chars.length - 1;

while(p2 > p1) {
if(chars[p1] != chars[p2]) {
int k = p2;
while(k > p1 && chars[k] != chars[p1]) k--;

if(k == p1) { //When no matching character found
swap(chars, p1, p1 + 1);
totalSwaps++;

} else { //When Matching character found swap until K reaches p2 position
while(k < p2) {
swap(chars, k, k + 1);
totalSwaps++;
k++;
}
p1++; p2--;
}
} else {
p1++; p2--; //When the characters are equal move on
}
}
}
else return -1;
}

private static void swap(char[] chars, int k, int i) {
char temp = chars[k];
chars[k] = chars[i];
chars[i] = temp;
}

private boolean isShuffledPalindrome(String s) {
int [] occurrence = new int;
int oddCount = 0;

for(int i = 0; i < s.length(); i++) occurrence[s.charAt(i) - 'a']++;
for (int value : occurrence) if (value % 2 != 0) oddCount++;
return oddCount <= 1;
}```

Program C++:

General idea of the algorithm:
palindrome has mirrored sides where letters on the same distance from the middle of the word are the same.

1. Check if given string is a shuffled palindrome. If no return -1.
2. We checking if the letters from both sides are the same stared from edges of the word toward the center
If the check is OK for all letters we return 0 because it is a correct palindrome and we should move nothing.
3. If we meet different letters we trying to find the same letter going from the end to the beginning of the word
2.1. If we meet the same letter we shift it by swaps to it’s right place and return to the phase 1
2.2. If we don’t meed the same letter we swap the first letter with it’s neighbour and return to the phase 1.
4. Count all swaps and return the number.

Algorithm:
1. First check the given string is a jumbled/shuffled palindrome or not.
2. Next have two pointers p1 at 0 and p2 at s.length – 1 and start iterating.
3. If chars at both the pointers are same then just shrink the window (increase the p1 and decrease the p2).
4. or Else
a. find the matching pair and swap the char to p2 index (increase swap count while swapping) and finally shrink the window.
b. if not found just swap once with adjacent index and increase the swap count (do not shrink the window here)
5. Print the Swap Count

Time Complexity: O(n) to find Palindrome + [ O(n) for two pointer iteration * O(n) for checking and swapping ] so => O(n^2)
Space Complexity: O(n)

```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_palindrom(const string & word){
int i1 = 0;
int i2 = word.size() - 1;
while (i2 > i1) {
if (word[i1] != word[i2]) {
return false;
}
++i1;
--i2;
}
return true;
}

bool is_shuffled_palindrome(const string & s) {
vector<int> occurrence(26, 0);
int odd_count = 0;

for(char i : s) { occurrence[i - 'a']++; }
for (int value : occurrence) {
if (value % 2 != 0) {
odd_count++;
}
}
return odd_count <= 1;
}

/*
int solution(string s) {
int start = 0;
int end = s.size() - 1;
int result = 0;
while (start < end) {
// if we found different chars
if (s[start] != s[end]) {
int i = end; // make an additional iterator from the end

// move toward the start until we found the same char
while (i > start && s[i] != s[start]) { --i; }

// if we have not scanned whole string yet
if (i > start) {
// swap all chars from i to the end
while (i < end) {
swap(s[i], s[i + 1]);
result++;
i++;
}
}
// if we scanned whole the string and found
// it needs for case when the first char is not on it's right place
// all other parts of the algorithm don't process a char on the start
// we don't need to shrink the processing window here so we start
// a new iteration of the loop here.
else {
swap(s[start], s[start+1]);
result++;
continue;
}
}
// if s[start] == s[end] shrink the processing window
start++;
end--;
}
return result;
}
*/

int solution(string s) {
int s_size = s.size();
int result = 0;
int start = 0, end = s_size - 1;

// if string is empty or it is not a palindrome return -1
if ((s_size == 0) || (!is_shuffled_palindrome(s))) {
return -1;
}

while (end > start) {
// if we found different chars
if (s[start] != s[end]) {
int i = end; // make an additional iterator from the end

// move toward the start until we found the same char
while (i > start && s[i] != s[start]) { --i; }

// if we scanned whole the string and found
// it needs for case when the first char is not on it's right place
// all other parts of the algorithm don't process a char on the start
if (i == start) {
swap(s[start], s[start + 1]);
++result;
}
// if the same character found swap all chars from i to the end
else {
while (i < end) {
swap(s[i], s[i + 1]);
++result;
++i;
}
++start; --end;
}
}
// if s[start] == s[end] shrink the processing window
else {
++start; --end;
}
}
return result;
}

int main() {
cout << solution("abcba") << endl;
cout << solution("ntaiain") << endl;
cout << solution("niaiatn") << endl;
cout << solution("damam") << endl;