Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

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