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.
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.
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.
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.
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.
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.
We now solve this problem for the next cell "abb".
On applying the formula in figure 1, we get the following answer.
Hence, the given cell stores the maximum of the cell to its left and the cell below it. Hence the answer is 2.
Similarly, we want you to fill the rest of the array and check your final result with figure 9.
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.