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

Problems
1

https://algo.monster/problems/min_swaps_to_make_palindrome

2

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

3

You are right. We will fix this.

4

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.

5

which general pattern does this fall under?

6

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)

7

function minSwaps(inp) {
// WRITE YOUR BRILLIANT CODE HERE
// https://www.youtube.com/watch?v=JQ1_7eEPloI
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;

}

8

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

9

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

10

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

11

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;
}
12

middle is not a palindrome

1 Like
13

Yeah how did middle become a palindrome?