Redirecting to
NADOS


  Prev   Next

Minimum Insertions To Make Palindrome







A long descriptive name is better than a short enigmatic name. A long descriptive name is better than a long descriptive comment.

Minimum Insertions To Make Palindrome

Hey there. We are going to solve the problem "Minimum Insertions to make Palindrome" in this article.

If you haven't gone through the problem, we suggest you do it now.


Important Links : Problem Link, Solution Video


You are given a string (str) and you have to find the minimum number of characters to be inserted to convert it to a palindrome.

WHAT

Let's understand it through an example. The input string is "abbcabda".

We first find out the Longest Palindromic Subsequence (LPS) of the input string. For the given string it comes out to be "ababa".

You must be familiar with the following process for finding LPS which has already been discussed.

img

Now we need to insert the remaining characters left in the given string "abbcabda" i.e. the characters of "abbcabda" excluding the characters in "ababa". Hence characters corresponding to 'b', 'c' and 'd' are to be inserted such that a palindrome is formed.

img

In figure 2, the characters marked with green dots are the inserted characters corresponding to the remaining characters.

You can see below in the final string "adbbcacbbda", every character has a corresponding character. Hence it is a palindromic string.

img

From this approach, we arrive at the conclusion that the minimum number of insertions is the difference between the length of the input string and the length of the Longest Palindromic subsequence.

According to this, for the given example the answer is 8-5=3.

DYNAMIC PROGRAMMING

If you have studied the problem of Longest Palindromic Subsequence then you will have no problem in solving its dp array.

  • Reader, we make a dp array of dimensions str.length() * str.length(). One of the axes denotes the start index (si) and the other denotes the end index (ei).
    Also, the array is solved diagonally.
    img
    The marked cell in figure 3 stores the length of the Longest Palindromic Subsequence for the string starting from b2 and ending at b5 i.e. "bcab".
  • You already know that as shown in Figure 5, since "ei" cannot come before "si", therefore the following cells store no value.
    img
  • For a string of length 1, the longest Palindromic Subsequence must be of length 1 too.
    From figure 1, for length 2, if the characters are equal then answer is 2 else it is one.
    img
  • We now solve this problem for the next cell "abb".
    On applying the formula in figure 1, we get the following answer.
    img

Hence, the given cell stores the maximum of the cell to its left and the cell below it. Hence the answer is 2.

img
  • Similarly, we want you to fill the rest of the array and check your final result with figure 9.
    img
  • Reader you know that our LPS is stored in the upper right corner cell dp[0][dp.leength-1] because it stores the result for the string starting from a0 and ending at a7 i.e. "abbcabda".
  • As already discussed, minimum insertions= length of input string-length of LPS.
    Hence we return 8-5=3.

If you need any help in filling the dp array just refer to the solution video .

CODE

Dear coder, we are sure that if you have coded the LPS problem previously and paid close attention to the above discussion, then you will find the code given below quite straightforward.

import java.io.*; import java.util.*; public class Main { public static int solution(String str) { int[][]dp=new int[str.length()][str.length()]; for(int gap=0;gap< dp.length;gap++){ for(int si=0,ei=gap;ei< dp.length;si++,ei++){ if(gap==0){ dp[si][ei]=1; }else{ if(str.charAt(si)==str.charAt(ei)){ dp[si][ei]=dp[si+1][ei-1]+2; }else{ dp[si][ei]=Math.max(dp[si+1][ei],dp[si][ei-1]); } } } } int ans=str.length()-dp[0][dp.length-1]; return ans; } public static void main(String[] args) { Scanner scn = new Scanner(System.in); String str = scn.next(); System.out.println(solution(str)); } }
java; true";
Analysis
Time Complexity:

O(n2)

Space Complexity:

O(n2)

In case you have any gaps in your understanding, we suggest you watch the solution video.

Here, we conclude our discussion. We'll see you in the next question.

Minimum Insertions to make Palindrome
Dynamic Programming and Greedy
Author: Shreeya Gupta
 
Run
Id Name