Minimum insertions to form a palindrome with permutations allowed

The problem “Minimum insertions to form a palindrome with permutations allowed” states that you are given a String with all letters in lowercase. The problem statement asks to find out the minimum insertion of a character to a string that it can become Palindrome. The position of characters can be changed in a string.

Example

malyalam

1

Explanation

If we can add ‘a’ to the initial string, we can create a palindrome.

madaam

1

Explanation

Either add ‘d’ or ‘a’ to make the original string palindrome.

Algorithm

1. Set length of the string to l and output to 0.
2. Declare an integer array.
3. Store and maintain the count of each character in a string.
4. Traverse the array starting from 0 to while i < 26.
   1. Check if countChar[i] % 2 == 1,
      1. If true, then do output++.
5. If the output is equal to 0, then return 0.
6. Else return output-1.

Explanation

You are given a string, your task given is to find out the minimum insertion to be done in a string so that it becomes a Palindrome. The position of characters can be changed in a string. We are going to count the occurrence of the character of a string and store it to an array. Because the idea behind is that when a string is a palindrome, there is only a single character that can be odd when the string length is odd. Other than that all characters have even frequency. So we need to find characters that occur an odd number of times.

We are going to count every character in the input string and store it to an array. As we already mentioned, a string which is palindrome can only have one character which occurs odd number of times. So the output would be one less than the character count. After storing every character string occurrence in an array. We are then making an array traversing from i=0 to i is less than 26. This is because there are a total of 26 characters and we should suppose that there will be a probability of occurrence of 26 characters in a given string.

While traversing the array, we will check if dividing each count by 2 leaves a remainder 1 if it is true, then it will increase the count of output by 1(output++ ). After traversing an array, if count remains as zero, means we find nothing in character which is odd means the string is already palindrome, we will return 0 else we will return (output-1) as we already mentioned output will be one less than the character count and hence we got output.

Code

C++ code to find Minimum insertions to form a palindrome with permutations allowed

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}

1

Java code to find Minimum insertions to form a palindrome with permutations allowed

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}

1

Complexity Analysis

Time Complexity

O(n) where “n” is the number of characters in the input string.

Space Complexity

O(1), because we have created an extra array having constant size. Thus the space complexity is constant.