Best solutions for Microsoft interview tasks. Min Swaps to Make Palindrome.

Description:

Given a string, what is the minimum number of adjacent swaps required to convert a string into a palindrome. If not possible, return -1.

Example 1: Input: “mamad” Output: 3

Example 2: Input: “asflkj” Output: -1

Example 3: Input: “aabb” Output: 2

Example 4: Input: “ntiin” Output: 1

Explanation: swap ‘t’ with ‘i’ => “nitin”

Solution:

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam, racecar. https://en.wikipedia.org/wiki/Palindrome

As you can see all palindromes words have two mirrored parts. It means that letters on the same distance from the middle of the word are the same.

We may base our algorithm on this feature.

General idea of the algorithm:

0. Check if given string is a shuffled palindrome. If no return -1.
1. Then we checking if the letters from both sides are the same, moving 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;
2. 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 neighbor and return to the phase 1;
3. Count all swaps and return the number.

Assume that we may have in the string only lower case English letters. Lets make two pointers or iterators to the begin and to the end of the string. Lets call the iterators start and end and will process the string from both sides towards each other.

1. We comparing the characters from the begin and the end while they are the same. If we have processed whole the string it means our word is a palindrome and we should return 0 because we don’t need to swap characters.

2. If in process of comparing characters described above we meet two different characters at the begin and at the end of the processing window (between start and end iterators) we switch to another algorithm.

3. We make an additional iterator from the end, lets call it i, and scan the processing window from the end iterator toward the start iterator. During the scan we compare all characters with a character pointed by start iterator. If we meet no one the same character as on the start it means the word it not a palindrome or that the first character is not on it’s right place and should be moved. To solve this dilemma we need to add check if the string contains correct palindrome. Thus if we are sure that we work with a palindrome we should swap the character on the start with adjacent character, count this swap and back to the phase 1 with the same start and end iterators.

4. In case we meet the same character we should swap all characters from i to the end iterator and count the swaps. Then we return to the phase 1.

Return number of the counted swaps at the end of the algorithm.

Time Complexity: O(n) for two pointer iteration * O(n) for checking and swapping == O(n²)

Space Complexity: O(n)

The algorithm of the check if we have a shuffled palindrome is simple. We should make an array of integers for 26 English letter which we may meet in the string and count number of each letter met in the word. If we have a shuffled palindrome all letters we meet even times except one letter in the middle of the word for odd size of string.

Implementation of the check:

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

C++ implementation of the solution:

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

Repository with the full project you can find here: https://github.com/jolly-fellow/microsoft/tree/master/min_swaps_to_make_palindrome

Return to the table of contents.