# 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

1 Like

Yeah how did middle become a palindrome?