# Minimum Adj Swaps to Make Palindrome - Company-specific OAs / Microsoft OA

This code does not work.
Input dmaam gives -1.

You are right. We will fix this.

The old code didn’t consider the case for the single character in the middle of the palindrome. The new code should be working now.

which general pattern does this fall under?

Time complexity : O(n) to find the palindrome + [O(n/2) for left and right ptr iteration * O(n/2) for checking and swapping] ~ O(n^2)
Space complexity : O(n)

function minSwaps(inp) {
// WRITE YOUR BRILLIANT CODE HERE
let str = inp.split(“”);

``````function isFeasible(str){
let chCountArr = new Array(26).fill(0);
let oddCount = 0;

for(let i=0; i < str.length; i++){
let idx = str[i].charCodeAt(0) - 'a'.charCodeAt(0);
chCountArr[idx]++;
}

for(let i=0; i < chCountArr.length; i++){
if(chCountArr[i] % 2 == 1){
oddCount++;
}
}

return oddCount <= 1;
}

function swap(arr, i, j){
let t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

if(!isFeasible(str)){
return -1;
}

let minSwapCount = 0;

let left=0, right = str.length-1;

while(left < right){

if(str[left] == str[right]){
left++;
right--;
}else{
let k = right;
while(left < k && str[left] != str[k]){
k--;
}

if(left == k){
swap(str, left, left+1);
minSwapCount++;
}else{
swap(str, k, k+1);
minSwapCount++;
}

}
}

return minSwapCount;
``````

}

I’d love if we could get an explanation for this. Just to help with understanding.

Why is the answer 3 in the last example? “middle” is not a palindrome.

I am confused here too, “middle” is clearly not a palindrome. Any explanation for this @MOD?

public int countSwapInPalindrome(String s){
int length = s.length();
if (length == 0 || length == 1) return -1;

``````    char[] str = s.toCharArray();
int start = 0, end = length - 1;
int count = 0;
while (start < end) {
if (str[start] != str[end]){
boolean isSwapped = false;
for (int i = start + 1; i < end; i++){
if (str[start] == str[i]){
char temp = str[i];
str[i] = str[end];
str[end] = temp;
count++;
isSwapped = true;
break;
}else if (str[end] == str[i]){
char temp = str[i];
str[i] = str[start];
str[start] = temp;
count++;
isSwapped = true;
break;
}
}
if (!isSwapped) return -1;
}
start++;
end--;
}

return (s.equals(String.valueOf(str))) ? -1 : count;
}
``````

middle is not a palindrome