Given string str, the task is to find the minimum number of characters to be inserted to convert it to a palindrome.
Before we go further, let us understand with a few examples:
- ab: Number of insertions required is 1 i.e. bab
- aa: Number of insertions required is 0 i.e. aa
- abcd: Number of insertions required is 3 i.e. dcbabcd
- abcda: Number of insertions required is 2 i.e. adcbcda which is the same as the number of insertions in the substring bcd(Why?).
- abcde: Number of insertions required is 4 i.e. edcbabcde
Let the input string be str[l……h]. The problem can be broken down into three parts:
- Find the minimum number of insertions in the substring str[l+1,…….h].
- Find the minimum number of insertions in the substring str[l…….h-1].
- Find the minimum number of insertions in the substring str[l+1……h-1].
Recursive Approach: The minimum number of insertions in the string str[l…..h] can be given as:
- minInsertions(str[l+1…..h-1]) if str[l] is equal to str[h]
- min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1 otherwise
Below is the implementation of the above approach:
C++
// A Naive recursive program to find minimum // number insertions needed to make a string // palindrome #include<bits/stdc++.h> using namespace std; // Recursive function to find // minimum number of insertions int findMinInsertions(char str[], int l, int h) { // Base Cases if (l > h) return INT_MAX; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and last characters are // same. On the basis of the comparison result, // decide which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1): (min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1); } // Driver code int main() { char str[] = "neveropen"; cout << findMinInsertions(str, 0, strlen(str) - 1); return 0; } // This code is contributed by // Akanksha Rai |
C
// A Naive recursive program to find minimum // number insertions needed to make a string // palindrome #include <stdio.h> #include <limits.h> #include <string.h> // A utility function to find minimum of two numbers int min(int a, int b) { return a < b ? a : b; } // Recursive function to find minimum number of // insertions int findMinInsertions(char str[], int l, int h) { // Base Cases if (l > h) return INT_MAX; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and last characters are // same. On the basis of the comparison result, // decide which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1): (min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1); } // Driver program to test above functions int main() { char str[] = "neveropen"; printf("%d", findMinInsertions(str, 0, strlen(str)-1)); return 0; } |
Java
// A Naive recursive Java program to find minimum // number insertions needed to make a string // palindrome import java.util.*; import java.io.*; class GFG { // Recursive function to find minimum number // of insertions static int findMinInsertions(char str[], int l, int h) { // Base Cases if (l > h) return Integer.MAX_VALUE; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and last characters // are same. On the basis of the comparison // result, decide which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1): (Integer.min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1); } // Driver program to test above functions public static void main(String args[]) { String str= "neveropen"; System.out.println(findMinInsertions(str.toCharArray(), 0, str.length()-1)); } } // This code is contributed by Sumit Ghosh |
Python 3
# A Naive recursive program to find minimum # number insertions needed to make a string # palindrome import sys # Recursive function to find minimum # number of insertions def findMinInsertions(str, l, h): # Base Cases if (l > h): return sys.maxsize if (l == h): return 0 if (l == h - 1): return 0 if(str[l] == str[h]) else 1 # Check if the first and last characters are # same. On the basis of the comparison result, # decide which subproblem(s) to call if(str[l] == str[h]): return findMinInsertions(str, l + 1, h - 1) else: return (min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1) # Driver Code if __name__ == "__main__": str = "neveropen" print(findMinInsertions(str, 0, len(str) - 1)) # This code is contributed by ita_c |
C#
// A Naive recursive C# program // to find minimum number // insertions needed to make // a string palindrome using System; class GFG { // Recursive function to // find minimum number of // insertions static int findMinInsertions(char []str, int l, int h) { // Base Cases if (l > h) return int.MaxValue; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and // last characters are same. // On the basis of the // comparison result, decide // which subproblem(s) to call return (str[l] == str[h])? findMinInsertions(str, l + 1, h - 1): (Math.Min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1); } // Driver Code public static void Main() { string str= "neveropen"; Console.WriteLine(findMinInsertions(str.ToCharArray(), 0, str.Length - 1)); } } // This code is contributed by Sam007 |
Javascript
<script> // A Naive recursive JavaScript program to find minimum // number insertions needed to make a string // palindrome // Recursive function to find minimum number // of insertions function findMinInsertions(str,l,h) { // Base Cases if (l > h) return Number.MAX_VALUE; if (l == h) return 0; if (l == h - 1) return (str[l] == str[h])? 0 : 1; // Check if the first and last characters // are same. On the basis of the comparison // result, decide which subproblem(s) to call return (str[l] == str[h]) ? findMinInsertions(str, l + 1, h - 1) : (Math.min(findMinInsertions(str, l, h - 1), findMinInsertions(str, l + 1, h)) + 1) } // Driver program to test above functions let str= "neveropen"; document.write(findMinInsertions(str,0, str.length-1)); // This code is contributed by rag2127 </script> |
Output
3
Time Complexity: O(2n)
Auxiliary Space: O(n)
Dynamic Programming based Solution
If we observe the above approach carefully, we can find that it exhibits overlapping subproblems.
Suppose we want to find the minimum number of insertions in string “abcde”:
abcde
/ | \
/ | \
bcde abcd bcd <- case 3 is discarded as str[l] != str[h]
/ | \ / | \
/ | \ / | \
cde bcd cd bcd abc bc
/ | \ / | \ /|\ / | \
de cd d cd bc c………………….
The substrings in bold show that the recursion is to be terminated and the recursion tree cannot originate from there. Substring in the same color indicates overlapping subproblems.
How to re-use solutions of subproblems? The memorization technique is used to avoid similar subproblem recalls. We can create a table to store the results of subproblems so that they can be used directly if the same subproblem is encountered again.
The below table represents the stored values for the string abcde.
a b c d e ---------- 0 1 2 3 4 0 0 1 2 3 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0
How to fill the table?
The table should be filled in a diagonal fashion. For the string abcde, 0….4, the following should be ordered in which the table is filled:
Gap = 1: (0, 1) (1, 2) (2, 3) (3, 4) Gap = 2: (0, 2) (1, 3) (2, 4) Gap = 3: (0, 3) (1, 4) Gap = 4: (0, 4)
Below is the implementation of the above approach:
C++
// A Dynamic Programming based program to find // minimum number insertions needed to make a // string palindrome #include <bits/stdc++.h> using namespace std; // A DP function to find minimum // number of insertions int findMinInsertionsDP(char str[], int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int table[n][n], l, h, gap; // Initialize all table entries as 0 memset(table, 0, sizeof(table)); // Fill the table for (gap = 1; gap < n; ++gap) for (l = 0, h = gap; h < n; ++l, ++h) table[l][h] = (str[l] == str[h])? table[l + 1][h - 1] : (min(table[l][h - 1], table[l + 1][h]) + 1); // Return minimum number of insertions // for str[0..n-1] return table[0][n - 1]; } // Driver Code int main() { char str[] = "neveropen"; cout << findMinInsertionsDP(str, strlen(str)); return 0; } // This is code is contributed by rathbhupendra |
C
// A Dynamic Programming based program to find // minimum number insertions needed to make a // string palindrome #include <stdio.h> #include <string.h> // A utility function to find minimum of two integers int min(int a, int b) { return a < b ? a : b; } // A DP function to find minimum number of insertions int findMinInsertionsDP(char str[], int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int table[n][n], l, h, gap; // Initialize all table entries as 0 memset(table, 0, sizeof(table)); // Fill the table for (gap = 1; gap < n; ++gap) for (l = 0, h = gap; h < n; ++l, ++h) table[l][h] = (str[l] == str[h])? table[l+1][h-1] : (min(table[l][h-1], table[l+1][h]) + 1); // Return minimum number of insertions for // str[0..n-1] return table[0][n-1]; } // Driver program to test above function. int main() { char str[] = "neveropen"; printf("%d", findMinInsertionsDP(str, strlen(str))); return 0; } |
Java
// A Java solution for Dynamic Programming // based program to find minimum number // insertions needed to make a string // palindrome import java.io.*; import java.util.Arrays; class GFG { // A DP function to find minimum number // of insertions static int findMinInsertionsDP(char str[], int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int table[][] = new int[n][n]; int l, h, gap; // Fill the table for (gap = 1; gap < n; ++gap) for (l = 0, h = gap; h < n; ++l, ++h) table[l][h] = (str[l] == str[h])? table[l+1][h-1] : (Integer.min(table[l][h-1], table[l+1][h]) + 1); // Return minimum number of insertions // for str[0..n-1] return table[0][n-1]; } // Driver program to test above function. public static void main(String args[]) { String str = "neveropen"; System.out.println( findMinInsertionsDP(str.toCharArray(), str.length())); } } // This code is contributed by Sumit Ghosh |
Python3
# A Dynamic Programming based program to # find minimum number insertions needed # to make a string palindrome # A utility function to find minimum # of two integers def Min(a, b): return min(a, b) # A DP function to find minimum number # of insertions def findMinInsertionsDP(str1, n): # Create a table of size n*n. table[i][j] # will store minimum number of insertions # needed to convert str1[i..j] to a palindrome. table = [[0 for i in range(n)] for i in range(n)] l, h, gap = 0, 0, 0 # Fill the table for gap in range(1, n): l = 0 for h in range(gap, n): if str1[l] == str1[h]: table[l][h] = table[l + 1][h - 1] else: table[l][h] = (Min(table[l][h - 1], table[l + 1][h]) + 1) l += 1 # Return minimum number of insertions # for str1[0..n-1] return table[0][n - 1]; # Driver Code str1 = "neveropen"print(findMinInsertionsDP(str1, len(str1))) # This code is contributed by # Mohit kumar 29 |
C#
// A C# solution for Dynamic Programming // based program to find minimum number // insertions needed to make a string // palindrome using System; class GFG { // A DP function to find minimum number // of insertions static int findMinInsertionsDP(char []str, int n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. int [,]table = new int[n, n]; int l, h, gap; // Fill the table for (gap = 1; gap < n; ++gap) for (l = 0, h = gap; h < n; ++l, ++h) table[l, h] = (str[l] == str[h])? table[l+1, h-1] : (Math.Min(table[l, h-1], table[l+1, h]) + 1); // Return minimum number of insertions // for str[0..n-1] return table[0, n-1]; } // Driver code public static void Main() { String str = "neveropen"; Console.Write( findMinInsertionsDP(str.ToCharArray(), str.Length)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // A Javascript solution for Dynamic Programming // based program to find minimum number // insertions needed to make a string // palindrome // A DP function to find minimum number // of insertions function findMinInsertionsDP(str,n) { // Create a table of size n*n. table[i][j] // will store minimum number of insertions // needed to convert str[i..j] to a palindrome. let table=new Array(n); for(let i=0;i<n;i++) { table[i]=new Array(n); } for(let i=0;i<n;i++) { for(let j=0;j<n;j++) { table[i][j]=0; } } let l=0, h=0, gap=0; // Fill the table for (gap = 1; gap < n; gap++) { for (l = 0, h = gap; h < n; l++, h++) { table[l][h] = (str[l] == str[h]) ? table[l+1][h-1] : (Math.min(table[l][h-1],table[l+1][h]) + 1); } } // Return minimum number of insertions // for str[0..n-1] return table[0][n - 1]; } // Driver program to test above function. let str = "neveropen"; document.write(findMinInsertionsDP(str, str.length)); // This code is contributed by avanitrachhadiya2155 </script> |
Output
3
Time complexity: O(N2)
Auxiliary Space: O(N2)
Another Dynamic Programming Solution (Variation of Longest Common Subsequence Problem)
The problem of finding minimum insertions can also be solved using Longest Common Subsequence (LCS) Problem. If we find out the LCS of string and its reverse, we know how many maximum characters can form a palindrome. We need to insert the remaining characters. Following are the steps.
- Find the length of LCS of the input string and its reverse. Let the length be ‘l’.
- The minimum number of insertions needed is the length of the input string minus ‘l’.
Below is the implementation of the above approach:
C++
// An LCS based program to find minimum number // insertions needed to make a string palindrome #include <bits/stdc++.h> using namespace std; // Returns length of LCS for X[0..m-1], Y[0..n-1]. int lcs( string X, string Y, int m, int n ) { int L[m+1][n+1]; int i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i - 1] == Y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1; else L[i][j] = max(L[i - 1][j], L[i][j - 1]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } void reverseStr(string& str) { int n = str.length(); // Swap character starting from two // corners for (int i = 0; i < n / 2; i++) swap(str[i], str[n - i - 1]); } // LCS based function to find minimum number of // insertions int findMinInsertionsLCS(string str, int n) { // Create another string to store reverse of 'str' string rev = ""; rev = str; reverseStr(rev); // The output is length of string minus length of lcs of // str and it reverse return (n - lcs(str, rev, n, n)); } // Driver code int main() { string str = "neveropen"; cout << findMinInsertionsLCS(str, str.length()); return 0; } // This code is contributed by rathbhupendra |
C
// An LCS based program to find minimum number // insertions needed to make a string palindrome #include<stdio.h> #include <string.h> /* Utility function to get max of 2 integers */int max(int a, int b) { return (a > b)? a : b; } /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */int lcs( char *X, char *Y, int m, int n ) { int L[m+1][n+1]; int i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i=0; i<=m; i++) { for (j=0; j<=n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i-1] == Y[j-1]) L[i][j] = L[i-1][j-1] + 1; else L[i][j] = max(L[i-1][j], L[i][j-1]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } // LCS based function to find minimum number of // insertions int findMinInsertionsLCS(char str[], int n) { // Create another string to store reverse of 'str' char rev[n+1]; strcpy(rev, str); strrev(rev); // The output is length of string minus length of lcs of // str and it reverse return (n - lcs(str, rev, n, n)); } // Driver program to test above functions int main() { char str[] = "neveropen"; printf("%d", findMinInsertionsLCS(str, strlen(str))); return 0; } |
Java
// An LCS based Java program to find minimum // number insertions needed to make a string // palindrome import java.util.*; import java.io.*; class GFG { /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */ static int lcs( String X, String Y, int m, int n ) { int L[][] = new int[m+1][n+1]; int i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i=0; i<=m; i++) { for (j=0; j<=n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X.charAt(i-1) == Y.charAt(j-1)) L[i][j] = L[i-1][j-1] + 1; else L[i][j] = Integer.max(L[i-1][j], L[i][j-1]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } // LCS based function to find minimum number // of insertions static int findMinInsertionsLCS(String str, int n) { // Using StringBuffer to reverse a String StringBuffer sb = new StringBuffer(str); sb.reverse(); String revString = sb.toString(); // The output is length of string minus // length of lcs of str and it reverse return (n - lcs(str, revString , n, n)); } // Driver program to test above functions public static void main(String args[]) { String str = "neveropen"; System.out.println( findMinInsertionsLCS(str, str.length())); } } // This code is contributed by Sumit Ghosh |
Python3
# An LCS based Python3 program to find minimum # number insertions needed to make a string # palindrome """ Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function """def lcs(X, Y, m, n) : L = [[0 for i in range(n + 1)] for j in range(m + 1)] """ Following steps build L[m + 1, n + 1] in bottom up fashion. Note that L[i, j] contains length of LCS of X[0..i - 1] and Y[0..j - 1] """ for i in range(m + 1) : for j in range(n + 1) : if (i == 0 or j == 0) : L[i][j] = 0 elif (X[i - 1] == Y[j - 1]) : L[i][j] = L[i - 1][j - 1] + 1 else : L[i][j] = max(L[i - 1][j], L[i][j - 1]) """ L[m,n] contains length of LCS for X[0..n-1] and Y[0..m-1] """ return L[m][n] # LCS based function to find minimum number # of insertions def findMinInsertionsLCS(Str, n) : # Using charArray to reverse a String charArray = list(Str) charArray.reverse() revString = "".join(charArray) # The output is length of string minus # length of lcs of str and it reverse return (n - lcs(Str, revString , n, n)) # Driver code Str = "neveropen" print(findMinInsertionsLCS(Str,len(Str))) # This code is contributed by divyehrabadiya07 |
C#
// An LCS based C# program to find minimum // number insertions needed to make a string // palindrome using System; class GFG { /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */ static int lcs( string X, string Y, int m, int n ) { int[,] L = new int[m + 1, n + 1]; int i, j; /* Following steps build L[m+1,n+1] in bottom up fashion. Note that L[i,j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) L[i, j] = 0; else if (X[i - 1] == Y[j - 1]) L[i, j] = L[i - 1, j - 1] + 1; else L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]); } } /* L[m,n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m,n]; } // LCS based function to find minimum number // of insertions static int findMinInsertionsLCS(string str, int n) { // Using charArray to reverse a String char[] charArray = str.ToCharArray(); Array.Reverse(charArray); string revString = new string(charArray); // The output is length of string minus // length of lcs of str and it reverse return (n - lcs(str, revString , n, n)); } // Driver code static void Main() { string str = "neveropen"; Console.WriteLine(findMinInsertionsLCS(str,str.Length)); } } // This code is contributed by mits |
Javascript
<script> // An LCS based Javascript program to find minimum // number insertions needed to make a string // palindrome /* Returns length of LCS for X[0..m-1], Y[0..n-1]. See http://goo.gl/bHQVP for details of this function */ function lcs(X, Y, m, n) { let L = new Array(m+1); for(let i = 0; i < m + 1; i++) { L[i] = new Array(n+1); for(let j = 0; j < n + 1; j++) { L[i][j] = 0; } } let i, j; /* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */ for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) L[i][j] = 0; else if (X[i - 1] == Y[j - 1]) L[i][j] = L[i - 1][j - 1] + 1; else L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]); } } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return L[m][n]; } // LCS based function to find minimum number // of insertions function findMinInsertionsLCS(str, n) { let revString = str.split('').reverse().join(''); // The output is length of string minus // length of lcs of str and it reverse return (n - lcs(str, revString , n, n)); } // Driver program to test above functions let str = "neveropen"; document.write(findMinInsertionsLCS(str, str.length)); // This code is contributed by unknown2108 </script> |
Output
3
Time complexity: O(N2)
Auxiliary Space: O(N2)
Space Optimization Method: The above code can be space optimized by using only 1d array instead of 2d array. In the dp table we only need previous row and current row elements.
C++
// An LCS based program to find minimum number // insertions needed to make a string palindrome #include <bits/stdc++.h> using namespace std; // Returns length of LCS for X[0..m-1], Y[0..n-1]. int lcs(string X, string Y, int m, int n) { vector<int> prev(n + 1, 0), curr(n + 1, 0); int i, j; for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) prev[j] = 0; else if (X[i - 1] == Y[j - 1]) curr[j] = prev[j - 1] + 1; else curr[j] = max(prev[j], curr[j - 1]); } prev = curr; } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return prev[n]; } void reverseStr(string& str) { int n = str.length(); // Swap character starting from two // corners for (int i = 0; i < n / 2; i++) swap(str[i], str[n - i - 1]); } // LCS based function to find minimum number of // insertions int findMinInsertionsLCS(string str, int n) { // Create another string to store reverse of 'str' string rev = ""; rev = str; reverseStr(rev); // The output is length of string minus length of lcs of // str and it reverse return (n - lcs(str, rev, n, n)); } // Driver code int main() { string str = "neveropen"; cout << findMinInsertionsLCS(str, str.length()); return 0; } // This code is contributed by Sanskar |
Java
/* Java program to implement an LCS based approach to find minimum number of insertions needed to make a string palindrome*/import java.io.*; public class GFG { // Returns length of LCS for X[0..m-1], Y[0..n-1]. static int Lcs(String X, String Y, int m, int n) { int[] prev = new int[n + 1]; int[] curr = new int[n + 1]; int i, j; for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) prev[j] = 0; else if (X.charAt(i - 1) == Y.charAt(j - 1)) curr[j] = prev[j - 1] + 1; else curr[j] = Math.max(prev[j], curr[j - 1]); } prev = curr; } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return prev[n]; } // LCS based function to find minimum number of // insertions static int FindMinInsertionsLCS(String str, int n) { // Create another string to store reverse of 'str' StringBuilder tmp = new StringBuilder(); tmp.append(str); tmp.reverse(); String rev = tmp.toString(); // The output is length of string minus length of // lcs of str and it reverse return (n - Lcs(str, rev, n, n)); } // Driver code public static void main(String[] args) { String str = "neveropen"; System.out.println( FindMinInsertionsLCS(str, str.length())); } } // This code is contributed by Karandeep1234 |
Python3
# An LCS based program to find minimum number # insertions needed to make a string palindrome # Returns length of LCS for X[0..m-1], Y[0..n-1]. def lcs(X, Y, m, n): prev = [0 for i in range(n+1)] curr = [0 for i in range(n+1)] for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: prev[j] = 0 elif X[i-1] == Y[j-1]: curr[j] = prev[j-1]+1 else: curr[j] = max(prev[j], curr[j-1]) prev = curr # L[m][n] contains length of LCS for X[0..n-1] # and Y[0..m-1] return prev[n] def reverseStr(str): return str[::-1] # LCS based function to find minimum number of # insertions def findMinInsertionsLCS(str, n): # Create another string to store reverse of 'str' rev = reverseStr(str) # The output is length of string minus length of lcs of # str and it reverse return (n - lcs(str, rev, n, n)) # Driver code if __name__ == "__main__": str = "neveropen" print(findMinInsertionsLCS(str, len(str))) # This Code is Contributed By Vivek Maddeshiya |
C#
/* C# program to implement an LCS based approach to find minimum number of insertions needed to make a string palindrome*/ using System; using System.Collections.Generic; class GFG { // Returns length of LCS for X[0..m-1], Y[0..n-1]. static int Lcs(string X, string Y, int m, int n) { int[] prev = new int[n + 1]; int[] curr = new int[n + 1]; int i, j; for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) prev[j] = 0; else if (X[i - 1] == Y[j - 1]) curr[j] = prev[j - 1] + 1; else curr[j] = Math.Max(prev[j], curr[j - 1]); } prev = curr; } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return prev[n]; } // LCS based function to find minimum number of // insertions static int FindMinInsertionsLCS(string str, int n) { // Create another string to store reverse of 'str' char[] tmp = str.ToCharArray(); Array.Reverse(tmp); string rev = new string(tmp); // The output is length of string minus length of // lcs of str and it reverse return (n - Lcs(str, rev, n, n)); } // Driver code static void Main(string[] args) { string str = "neveropen"; Console.WriteLine( FindMinInsertionsLCS(str, str.Length)); } } // This code is contributed by cavi4762 |
Javascript
// An LCS based program to find minimum number // insertions needed to make a string palindrome // Returns length of LCS for X[0..m-1], Y[0..n-1]. function lcs(X, Y, m, n) { var prev = new Array(n + 1).fill(0); var curr = new Array(n + 1).fill(0); let i, j; for (i = 0; i <= m; i++) { for (j = 0; j <= n; j++) { if (i == 0 || j == 0) prev[j] = 0; else if (X[i - 1] == Y[j - 1]) curr[j] = prev[j - 1] + 1; else curr[j] = Math.max(prev[j], curr[j - 1]); } prev = curr; } /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ return prev[n]; } function reverseStr(rever) { return rever.split("").reverse().join(""); } // LCS based function to find minimum number of // insertions function findMinInsertionsLCS(str, q) { // Create another string to store reverse of 'str' var rever = str.slice(); rev = reverseStr(rever); // The output is length of string minus length of lcs of // str and it reverse return q - lcs(str, rev, q, q); } // Driver code var str = "neveropen"; console.log(findMinInsertionsLCS(str, str.length)); |
Output
3
Time complexity: O(N2)
Auxiliary Space: O(N)
Related Article :
Minimum number of Appends needed to make a string palindrome
This article is compiled by Aarti_Rathi and Aashish Barnwal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
