Make delicious recipes!

Longest palindrome creation from a given string



Problem: Given a string, find the minimum number of characters which must be inserted to make the string a palindrome

    Example 1: Given string is abcd, then maximum insertions required=3 to make it dcbabcd

    Example 2: Given string is a, then maximum insertions required=0

    Example 3: Given string is aab, then maximum insertions required=1 to make it baab

    Example 4: Given string is abca, then maximum insertions required=1 to make it abcba


Solution: An exponential solution for this problem is as follows:

int minInsertionsToPalindrom(char str[], int start, int end)
{
    if (start > end) return -1; // error case
    if (start == end) return 0; // base case 1
    if (1 == end - start)
        return (str[start] == str[end])? 0 : 1; // base case 2
 
    // if ends of string match, then eliminate both the ends and 
    // find solution for remaining string
    if (str[start] == str[end])
        return minInsertionsToPalindrom(str, start+1, end-1);

    // else try both the remaining cases
    int case1 = minInsertionsToPalindrom(str, start, end-1);
    int case2 = minInsertionsToPalindrom(str, start+1, end);

    return min (case1, case2) + 1;
}


This can be improved to O(n2) by using dynamic programming as follows:

public class MinCharsToFormPalindrome 
{

    public static void main(String[] args) 
    {
        String s = "baacab";
        System.out.println(minInsertionsToPalindrom(s, s.length()));
    }




    static int minInsertionsToPalindrom(String s, int len)
    {
        char str[] = s.toCharArray();
        int lookup[][] = new int[len][len]; // initialized to 0

        // solve for all sub-strings of size 1, then 2 and so on till the end
        for (int strlength = 1; strlength < len; strlength++)
        {
            for (int l = 0, h = strlength; h < len; ++l, ++h)
            {
                lookup[l][h] = 
                    (str[l] == str[h]) ?
                        lookup[l+1][h-1] :
                        Math.min (lookup[l][h-1], lookup[l+1][h]) + 1;
                        
                printLookup (lookup, l, h , str, s);
            }
        }
                        
        return lookup[0][len-1];
    }
    
    
    
    // Debug function to print array and other variables
    static void printLookup (int [][] lookup, int l, int h, char str[], String s)
    {
        String msg = "Solving for string '" + s.substring(l,h+1) + "' of length " + (h-l+1) + " from l="+l +", h="+h;
        System.out.println("\n\n" + msg + "\n");
        
        
        System.out.print("   ");
        for (int j=0; j<str.length; j++)
            System.out.print(str[j] + ", ");
        System.out.println();
        
        
        for (int i=0; i<lookup.length; i++)
        {
            System.out.print(str[i]+", ");
            for (int j=0; j<lookup[i].length; j++)
                System.out.print(lookup[i][j] + ", ");
            System.out.println();
        }
    }
}



Sample Executions:

aaba
Solving for string 'aa' of length 2 from l=0, h=1 a, a, b, a, a, 0, 0, 0, 0, a, 0, 0, 0, 0, b, 0, 0, 0, 0, a, 0, 0, 0, 0, Solving for string 'ab' of length 2 from l=1, h=2 a, a, b, a, a, 0, 0, 0, 0, a, 0, 0, 1, 0, b, 0, 0, 0, 0, a, 0, 0, 0, 0, Solving for string 'ba' of length 2 from l=2, h=3 a, a, b, a, a, 0, 0, 0, 0, a, 0, 0, 1, 0, b, 0, 0, 0, 1, a, 0, 0, 0, 0, Solving for string 'aab' of length 3 from l=0, h=2 a, a, b, a, a, 0, 0, 1, 0, a, 0, 0, 1, 0, b, 0, 0, 0, 1, a, 0, 0, 0, 0, Solving for string 'aba' of length 3 from l=1, h=3 a, a, b, a, a, 0, 0, 1, 0, a, 0, 0, 1, 0, b, 0, 0, 0, 1, a, 0, 0, 0, 0, Solving for string 'aaba' of length 4 from l=0, h=3 a, a, b, a, a, 0, 0, 1, 1, a, 0, 0, 1, 0, b, 0, 0, 0, 1, a, 0, 0, 0, 0, No of character insertions: 1, Expected Palindrome = aabaa
abcd
Solving for string 'ab' of length 2 from l=0, h=1 a, b, c, d, a, 0, 1, 0, 0, b, 0, 0, 0, 0, c, 0, 0, 0, 0, d, 0, 0, 0, 0, Solving for string 'bc' of length 2 from l=1, h=2 a, b, c, d, a, 0, 1, 0, 0, b, 0, 0, 1, 0, c, 0, 0, 0, 0, d, 0, 0, 0, 0, Solving for string 'cd' of length 2 from l=2, h=3 a, b, c, d, a, 0, 1, 0, 0, b, 0, 0, 1, 0, c, 0, 0, 0, 1, d, 0, 0, 0, 0, Solving for string 'abc' of length 3 from l=0, h=2 a, b, c, d, a, 0, 1, 2, 0, b, 0, 0, 1, 0, c, 0, 0, 0, 1, d, 0, 0, 0, 0, Solving for string 'bcd' of length 3 from l=1, h=3 a, b, c, d, a, 0, 1, 2, 0, b, 0, 0, 1, 2, c, 0, 0, 0, 1, d, 0, 0, 0, 0, Solving for string 'abcd' of length 4 from l=0, h=3 a, b, c, d, a, 0, 1, 2, 3, b, 0, 0, 1, 2, c, 0, 0, 0, 1, d, 0, 0, 0, 0, No of character insertions: 3, Expected Palindrome = abcdcba
abca
Solving for string 'ab' of length 2 from l=0, h=1 a, b, c, a, a, 0, 1, 0, 0, b, 0, 0, 0, 0, c, 0, 0, 0, 0, a, 0, 0, 0, 0, Solving for string 'bc' of length 2 from l=1, h=2 a, b, c, a, a, 0, 1, 0, 0, b, 0, 0, 1, 0, c, 0, 0, 0, 0, a, 0, 0, 0, 0, Solving for string 'ca' of length 2 from l=2, h=3 a, b, c, a, a, 0, 1, 0, 0, b, 0, 0, 1, 0, c, 0, 0, 0, 1, a, 0, 0, 0, 0, Solving for string 'abc' of length 3 from l=0, h=2 a, b, c, a, a, 0, 1, 2, 0, b, 0, 0, 1, 0, c, 0, 0, 0, 1, a, 0, 0, 0, 0, Solving for string 'bca' of length 3 from l=1, h=3 a, b, c, a, a, 0, 1, 2, 0, b, 0, 0, 1, 2, c, 0, 0, 0, 1, a, 0, 0, 0, 0, Solving for string 'abca' of length 4 from l=0, h=3 a, b, c, a, a, 0, 1, 2, 1, b, 0, 0, 1, 2, c, 0, 0, 0, 1, a, 0, 0, 0, 0, No of character insertions: 1, Expected Palindrome = abcba



Final example execution for a larger string:

baacab

Solving for string 'ba' of length 2 from l=0, h=1

   b, a, a, c, a, b, 
b, 0, 1, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
c, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'aa' of length 2 from l=1, h=2

   b, a, a, c, a, b, 
b, 0, 1, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
c, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'ac' of length 2 from l=2, h=3

   b, a, a, c, a, b, 
b, 0, 1, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'ca' of length 2 from l=3, h=4

   b, a, a, c, a, b, 
b, 0, 1, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 0, 
a, 0, 0, 0, 0, 0, 0, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'ab' of length 2 from l=4, h=5

   b, a, a, c, a, b, 
b, 0, 1, 0, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 0, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'baa' of length 3 from l=0, h=2

   b, a, a, c, a, b, 
b, 0, 1, 1, 0, 0, 0, 
a, 0, 0, 0, 0, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 0, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'aac' of length 3 from l=1, h=3

   b, a, a, c, a, b, 
b, 0, 1, 1, 0, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 0, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'aca' of length 3 from l=2, h=4

   b, a, a, c, a, b, 
b, 0, 1, 1, 0, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 0, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'cab' of length 3 from l=3, h=5

   b, a, a, c, a, b, 
b, 0, 1, 1, 0, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 2, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'baac' of length 4 from l=0, h=3

   b, a, a, c, a, b, 
b, 0, 1, 1, 2, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 2, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'aaca' of length 4 from l=1, h=4

   b, a, a, c, a, b, 
b, 0, 1, 1, 2, 0, 0, 
a, 0, 0, 0, 1, 1, 0, 
a, 0, 0, 0, 1, 0, 0, 
c, 0, 0, 0, 0, 1, 2, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'acab' of length 4 from l=2, h=5

   b, a, a, c, a, b, 
b, 0, 1, 1, 2, 0, 0, 
a, 0, 0, 0, 1, 1, 0, 
a, 0, 0, 0, 1, 0, 1, 
c, 0, 0, 0, 0, 1, 2, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'baaca' of length 5 from l=0, h=4

   b, a, a, c, a, b, 
b, 0, 1, 1, 2, 2, 0, 
a, 0, 0, 0, 1, 1, 0, 
a, 0, 0, 0, 1, 0, 1, 
c, 0, 0, 0, 0, 1, 2, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'aacab' of length 5 from l=1, h=5

   b, a, a, c, a, b, 
b, 0, 1, 1, 2, 2, 0, 
a, 0, 0, 0, 1, 1, 2, 
a, 0, 0, 0, 1, 0, 1, 
c, 0, 0, 0, 0, 1, 2, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


Solving for string 'baacab' of length 6 from l=0, h=5

   b, a, a, c, a, b, 
b, 0, 1, 1, 2, 2, 1, 
a, 0, 0, 0, 1, 1, 2, 
a, 0, 0, 0, 1, 0, 1, 
c, 0, 0, 0, 0, 1, 2, 
a, 0, 0, 0, 0, 0, 1, 
b, 0, 0, 0, 0, 0, 0, 


No of character insertions:1,
Expected Palindrome = baacaab


In terms of loops, note how similar this problem is to:
  1. Max ways for boolean expression to be true
  2. Optimum matrix chain multiplication
All of these problems have an outer loop which starts with 1 or 2 elements and then gradually widens the scope of the problem being solved.

Using longest common subsequence approach


This problem is also very similar to the longest common subsequence problem.
If we can find the longest common subsequence between the given string and its reverse, then minimum number of insertions required is
    str.length() - maxCommonSubsequence




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal