A palindrome string is one that reads the same backward as well as forward.
You are given a string 'str'.
Find the minimum number of characters needed to insert in 'str' to make it a palindromic string.
Input: 'str' = "abca"
Output: 1
Explanation:
If we insert the character ‘b’ after ‘c’, we get the string "abcba", which is a palindromic string. Please note that there are also other ways possible.
The first line contains a string 'str', containing lowercase English letters i.e from ‘a’ to ‘z’.
The output contains a single integer denoting the minimum number of insertions needed to make 'str' palindrome.
You do not need to print anything; it has already been taken care of. Just implement the given function.
abca
1
If we insert the character ‘b’ after ‘c’, we get the string "abcba", which is a palindromic string. Please note that there are also other ways possible.
abcdefg
6
aaaaa
0
The expected time complexity is O(|str| ^ 2).
1 <= |str| <= 1000
Where |str| represents the length of the string 'str'.
Time Limit: 1 sec.
The very first approach can be to try all possible substrings of the string and minimize the ans among the valid ones.
Let’s understand with an example:
Consider the string 'str' = “abcca” .
O(2 ^ n), where 'n' is the length of the string.
In the worst case, at every step, we are making 2 recursive calls. Hence, the overall complexity is O(2 ^ n).
O(n), where 'n' is the length of the string.
In the worst case, extra space is used by the recursion stack which goes to a maximum depth of 'n'.
All tags
Sort by
Interview problems
JAVA-DP-TABULATION
public class Solution {
public static int minInsertion(String s1) {
int n=s1.length();
StringBuilder sb=new StringBuilder(s1);
String s2=sb.reverse().toString();
int[][] dp=new int[n+1][n+1];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0 || j==0)
{
dp[i][j]=0;
}else if(s1.charAt(i-1)==s2.charAt(j-1))
{
dp[i][j]=1+dp[i-1][j-1];
}else
{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
int ans=n-dp[n][n];
return ans;
}
}
Interview problems
DP || Best || 100 % || CP
int lps(string str, int n) {
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
if (str[i] == str[j]) {
dp[i][j] = 2 + (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
int minimumInsertions(string &str)
{
// Write your code here.
// Find LPS (Longest Palindrome Subsequence)
// and then Min Insertions : N - LPS
int n=str.size();
return n-lps(str,n);
}
Interview problems
Recurr || Base || easiest || 60% || C++
int lps(string str,int i,int j){
if(i==j)
return 1;
if(i>j)
return 0;
if(str[i]==str[j]){
return 2+lps(str,i+1,j-1);
}
return max(lps(str,i+1,j),lps(str,i,j-1));
}
int minimumInsertions(string &str)
{
// Write your code here.
// Find LPS (Longest Palindrome Subsequence)
// and then Min Insertions : N - LPS
return str.size()-lps(str,0,str.size()-1);
}
Interview problems
As simple as it could be in C++
int minimumInsertions(string &s)
{
// Write your code here.
int n=s.size();
string t=s;
reverse(s.begin(),s.end());
vector<vector<int>> v(n+1,vector<int>(n+1,0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(s[i]==t[j]){
v[i+1][j+1]=v[i][j]+1;
}
else{
v[i+1][j+1]=max(v[i+1][j],v[i][j+1]);
}
}
}
return n-v[n][n];
}
Interview problems
C++ || DP || LCS Approach
This questions is a variation of Longest Common Subsequence.
We know that longest palindrome of a string can be found by finding the lcs of string and reverse of string
Now after lcs is found, the remaining elements of input string will be the one not part of the palindrome. They are the ones whose duplicates are missing so they need to be added.
Eg: abca
Longest palindrome: aa
Remaining elements: bc
So elements to be added b & c
As we only need to return the numbers, we can find length of lps(lcs of string and reversed string) and subtract it from the length of the string.
In above example lps = 2 and string len = 4
Ans = 4 - 2 = 2
//function to find length of longest common subsequence
int LCS(string &x, string &y, int n, int m){
vector<vector<int>> t(n+1, vector<int>(m+1));
for(int i = 0; i<n+1; i++){
for(int j = 0; j<m+1; j++){
if(i==0 || j == 0){
t[i][j] = 0;
}
}
}
for(int i = 1; i<n+1; i++){
for(int j = 1; j<m+1; j++){
if(x[i-1]==y[j-1]){
t[i][j] = 1 + t[i-1][j-1];
}
else{
t[i][j] = max(t[i-1][j],t[i][j-1]);
}
}
}
return t[n][m];
}
//using string and reverse of string to find lcs helps find longest palindrome
//now elements remaining from longest palindrome in lcs can be deleted to make input string palindrom
//or their copy can be added to input string to make palindrome
int minimumInsertions(string &str)
{
// Write your code here.
string r = str;
reverse(str.begin(), str.end());
int n = str.length();
int x = LCS(str,r, n, n);
return str.length() - x;
}
Hope it helps!
Smallest and Simplest Code in C++!!
int minimumInsertions(string &str)
{
int n = str.size();
string s = str;
reverse(s.begin(), s.end());
vector<int> prev(n+1, 0), curr(n+1, 0);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(s[i-1] == str[j-1]) curr[j] = 1 + prev[j-1];
else curr[j] = max(curr[j-1], prev[j]);
}
prev = curr;
}
return n - prev[n];
}
Interview problems
DP - Tabulation
int minimumInsertions(string &str)
{
int n = str.length();
string t = str;
reverse(t.begin(), t.end());
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for(int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) {
if (str[i - 1] == t[j - 1])
dp[i][j] = 1 + dp[i - 1][j - 1];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return n - dp[n][n];
}Interview problems
C++ || DP || Simple || ✅✅
int minimumInsertions(string &str)
{
int n= str.size();
vector<vector<int>> dp(n+1,vector<int>(n+1,0));
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(str[i-1]==str[n-j]) dp[i][j] = 1+dp[i-1][j-1];
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return n-dp[n][n];
}Interview problems
DP SOLUTION || SPACE OPTIMIZATION
#include<bits/stdc++.h>
int minimumInsertions(string &str)
{
string t = str;
reverse(t.begin(),t.end());
int n = str.size();
// vector<vector<int>> dp(n+1,vector<int>(n+1,0));
vector<int> prev(n+1,0);
vector<int> curr(n+1,0);
for(int i = 1 ; i<=n ; i++){
for(int j = 1 ; j<=n ; j++){
if(str[i-1] == t[j-1]) curr[j] = 1 + prev[j-1];
else curr[j] = max(prev[j],curr[j-1]);
}
prev = curr;
}
int longestPalindrome = prev[n];
int ans = n - longestPalindrome;
return ans;
}
Interview problems
Space optimization (DP)
def minInsertion(str):
t=str[::-1]
n=len(str)
prev=cur=[0]*(n+1)
for i in range(n+1):
prev[i]=0
for i in range(1,n+1):
for j in range(1,n+1):
if str[i-1]==t[j-1]:
cur[j]=1+prev[j-1]
else:
cur[j]=max(prev[j],cur[j-1])
prev=cur[:]
return n- prev[n]
