Min Swaps to Make Palindrome Solution

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:
swap “ad” to get “mamda”
swap “md” to get “madma”
swap “ma” to get “madam”

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:
mamad
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

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

while True:
    s=input().strip()
    if s[0]=='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
                }
            }
            return totalSwaps;
        }
        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[26];
        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
                // no one the same char swap char on the start with adjacent char
                // 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
            // no one the same char swap char on the start with adjacent char
            // 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;
    cout << solution("mamad") << endl;

    return 0;
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA Online Assessment 2021 Questions and Answers

Microsoft Online Assessment 2021 Questions

Leave a Comment