Minimum insertions to make string palindrome

Understanding:

We need to find the minimum insertions required to make a string palindrome. Let us keep the “minimum” criteria aside and think, how can we make any given string palindrome by inserting characters.

The easiest way is to add the reverse of the string at the back of the original string as shown below. This will make any string palindrome.

Here the number of characters inserted will be equal to n (length of the string). This is the maximum number of characters we can insert to make strings palindrome.The problem states us to find the minimum of insertions. Let us try to figure it out:

To minimize the insertions, we will first try to refrain from adding those characters again which are already making the given string palindrome. For the given example, “aaa”, “aba”,”aca”, any of these are themselves palindromic components of the string. We can take any of them( as all are of equal length) and keep them intact. (let’s say “aaa”).

Now, there are two characters(‘b’ and ‘c’) remaining which prevent the string from being a palindrome. We can reverse their order and add them to the string to make the entire string palindrome.

We can do this by taking some other components (like “aca”) as well.
In order to minimize the insertions, we need to find the length of the longest palindromic component or in other words, the longest palindromic subsequence.

Minimum Insertion required = n(length of the string) - length of longest palindromic subsequence.

Approach:

We are given a string (say s), store its length as n.
Find the length of the longest palindromic subsequence ( say k) as discussed Longest Common Subsequence
Return (n-k) as answer.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    int lcs(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));

        // Initialize the first row and first column to 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] == s2[ind2 - 1])
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
                else
                    dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
            }
        }
        //Return the result
        return dp[n][m];
    }

    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    int longestPalindromeSubsequence(string s) {
        string t = s;
        reverse(s.begin(), s.end());
        return lcs(s, t);
    }
public:
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    int minInsertion(string s) {
        int n = s.size();
        int k = longestPalindromeSubsequence(s);

        /* The minimum insertions required is the 
        difference between the string length and 
        its longest palindromic subsequence length*/
        return n - k;
    }
};
int main() {
    string s = "abcaa";
    
    //Create an instance of Solution class
    Solution sol;
    
    // Call minInsertion function and print the result
    cout << "The Minimum insertions required to make string palindrome: " << sol.minInsertion(s);
    return 0;
}


import java.util.*;

class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    private int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        int[][] dp = new int[n + 1][m + 1];

        // Initialize the first row and first column to 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1.charAt(ind1 - 1) == s2.charAt(ind2 - 1))
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
                else
                    dp[ind1][ind2] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
            }
        }
        // Return the result
        return dp[n][m];
    }
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    private int longestPalindromeSubsequence(String s) {
        String t = new StringBuilder(s).reverse().toString();
        return lcs(s, t);
    }
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    public int minInsertion(String s) {
        int n = s.length();
        int k = longestPalindromeSubsequence(s);

        /* The minimum insertions required is the
        difference between the string length and
        its longest palindromic subsequence length*/
        return n - k;
    }

    public static void main(String[] args) {
        String s = "abcaa";
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call minInsertion function and print the result
        System.out.println("The Minimum insertions required to make string palindrome: " + sol.minInsertion(s));
    }
}
class Solution:
    """ Function to calculate the length 
    of the Longest Common Subsequence"""
    def lcs(self, s1, s2):
        n = len(s1)
        m = len(s2)

        dp = [[0] * (m + 1) for _ in range(n + 1)]

        # Initialize the first row and first column to 0
        for i in range(n + 1):
            dp[i][0] = 0
        for i in range(m + 1):
            dp[0][i] = 0

        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                if s1[ind1 - 1] == s2[ind2 - 1]:
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1]
                else:
                    dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1])
        
        # Return the result
        return dp[n][m]
        
    """ Function to calculate the length of 
    the Longest Palindromic Subsequence"""
    def longestPalindromeSubsequence(self, s):
        t = s[::-1]
        return self.lcs(s, t)

    """ Function to calculate the minimum insertions
    required to make a string palindrome"""
    def minInsertion(self, s):
        n = len(s)
        k = self.longestPalindromeSubsequence(s)

        """ The minimum insertions required is the
        difference between the string length and
        its longest palindromic subsequence length"""
        return n - k

if __name__ == "__main__":
    s = "abcaa"
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Call minInsertion function and print the result
    print("The Minimum insertions required to make string palindrome:", sol.minInsertion(s))
class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    lcs(s1, s2) {
        const n = s1.length;
        const m = s2.length;

        const dp = Array.from(Array(n + 1), () => Array(m + 1).fill(0));

        // Initialize the first row and first column to 0
        for (let i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }
        for (let i = 0; i <= m; i++) {
            dp[0][i] = 0;
        }

        for (let ind1 = 1; ind1 <= n; ind1++) {
            for (let ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] === s2[ind2 - 1])
                    dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
                else
                    dp[ind1][ind2] = Math.max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
            }
        }
        // Return the result
        return dp[n][m];
    }
    
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    longestPalindromeSubsequence(s) {
        const t = s.split('').reverse().join('');
        return this.lcs(s, t);
    }
    
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    minInsertion(s) {
        const n = s.length;
        const k = this.longestPalindromeSubsequence(s);

        /* The minimum insertions required is the
        difference between the string length and 
        its longest palindromic subsequence length*/
        return n - k;
    }
}

// Create an instance of Solution class
const sol = new Solution();

// Call minInsertion function and print the result
const s = "abcaa";
console.log("The Minimum insertions required to make string palindrome: " + sol.minInsertion(s));

Complexity Analysis:

Time Complexity: O(N*N), Where N is the length of the given string. As two nested loops are used to solve the problem.

Space Complexity: O(N*N), We are using an external array of size (N*N).

If we observe the relations obtained in tabultaion approach, dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]. We are using just two rows, dp[ind1-1][ ], dp[ind][ ], in order to calculate the present row.

So we are not required to contain an entire array, we can simply have two rows 'prev' and 'cur' where prev corresponds to dp[ind-1] and cur to dp[ind].

After declaring 'prev' and 'cur', replace dp[ind-1] to prev and dp[ind] with cur in the tabulation code. Following the same logic of tabulation, we will calculate cur[ind] in each iteration and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.

After end of the execution, return prev[n] (n is the length of the string), as our answer, as it will hold the cumulative result of the overall calculation.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    int lcs(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();

        /* Create two arrays to store the 
        previous and current rows of DP values*/
        vector<int> prev(m + 1, 0), cur(m + 1, 0);

        /* Base Case is covered as we have
        initialized the prev and cur to 0.*/

        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] == s2[ind2 - 1])
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = max(prev[ind2], cur[ind2 - 1]);
            }
            // Update the prev array with current values
            prev = cur;
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }

    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    int longestPalindromeSubsequence(string s) {
        string t = s;
        reverse(s.begin(), s.end());
        return lcs(s, t);
    }
public:
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    int minInsertion(string s) {
        int n = s.size();
        int k = longestPalindromeSubsequence(s);

        /* The minimum insertions required is the 
        difference between the string length and 
        its longest palindromic subsequence length*/
        return n - k;
    }
};
int main() {
    string s = "abcaa";
    
    //Create an instance of Solution class
    Solution sol;
    
    // Call minInsertion function and print the result
    cout << "The Minimum insertions required to make string palindrome: " << sol.minInsertion(s);
    return 0;
}


import java.util.*;

class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    private int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        /* Create two arrays to store the 
        previous and current rows of DP values */
        int[] prev = new int[m + 1];
        int[] cur = new int[m + 1];

        /* Base Case is covered as we have
        initialized the prev and cur to 0. */

        for (int ind1 = 1; ind1 <= n; ind1++) {
            for (int ind2 = 1; ind2 <= m; ind2++) {
                if (s1.charAt(ind1 - 1) == s2.charAt(ind2 - 1))
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
            }
            // Update the prev array with current values
            System.arraycopy(cur, 0, prev, 0, m + 1);
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    private int longestPalindromeSubsequence(String s) {
        String t = new StringBuilder(s).reverse().toString();
        return lcs(s, t);
    }
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    public int minInsertion(String s) {
        int n = s.length();
        int k = longestPalindromeSubsequence(s);

        /* The minimum insertions required is the
        difference between the string length and
        its longest palindromic subsequence length*/
        return n - k;
    }

    public static void main(String[] args) {
        String s = "abcaa";
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call minInsertion function and print the result
        System.out.println("The Minimum insertions required to make string palindrome: " + sol.minInsertion(s));
    }
}
class Solution:
    """ Function to calculate the length 
    of the Longest Common Subsequence"""
    def lcs(self, s1, s2):
        n = len(s1)
        m = len(s2)

        """ Create two arrays to store the 
        previous and current rows of DP values """
        prev = [0] * (m + 1)
        cur = [0] * (m + 1)

        """ Base Case is covered as we have
        initialized the prev and cur to 0. """

        for ind1 in range(1, n + 1):
            for ind2 in range(1, m + 1):
                if s1[ind1 - 1] == s2[ind2 - 1]:
                    cur[ind2] = 1 + prev[ind2 - 1]
                else:
                    cur[ind2] = max(prev[ind2], cur[ind2 - 1])
            """ Update the prev array with current values """
            prev = cur[:]
        
        # The value at prev[m] contains length of LCS
        return prev[m]
        
    """ Function to calculate the length of 
    the Longest Palindromic Subsequence"""
    def longestPalindromeSubsequence(self, s):
        t = s[::-1]
        return self.lcs(s, t)

    """ Function to calculate the minimum insertions
    required to make a string palindrome"""
    def minInsertion(self, s):
        n = len(s)
        k = self.longestPalindromeSubsequence(s)

        """ The minimum insertions required is the
        difference between the string length and
        its longest palindromic subsequence length"""
        return n - k

if __name__ == "__main__":
    s = "abcaa"
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Call minInsertion function and print the result
    print("The Minimum insertions required to make string palindrome:", sol.minInsertion(s))
class Solution {
    /* Function to calculate the length 
    of the Longest Common Subsequence*/
    lcs(s1, s2) {
        const n = s1.length;
        const m = s2.length;

        /* Create two arrays to store the 
        previous and current rows of DP values */
        const prev = new Array(m + 1).fill(0);
        const cur = new Array(m + 1).fill(0);

        /* Base Case is covered as we have
        initialized the prev and cur to 0. */

        for (let ind1 = 1; ind1 <= n; ind1++) {
            for (let ind2 = 1; ind2 <= m; ind2++) {
                if (s1[ind1 - 1] === s2[ind2 - 1])
                    cur[ind2] = 1 + prev[ind2 - 1];
                else
                    cur[ind2] = Math.max(prev[ind2], cur[ind2 - 1]);
            }
            /* Update the prev array with current values */
            for (let k = 0; k <= m; k++) {
                prev[k] = cur[k];
            }
        }
        // The value at prev[m] contains length of LCS
        return prev[m];
    }
    
    /* Function to calculate the length of 
    the Longest Palindromic Subsequence*/
    longestPalindromeSubsequence(s) {
        const t = s.split('').reverse().join('');
        return this.lcs(s, t);
    }
    
    /* Function to calculate the minimum insertions
    required to make a string palindrome*/
    minInsertion(s) {
        const n = s.length;
        const k = this.longestPalindromeSubsequence(s);

        /* The minimum insertions required is the
        difference between the string length and 
        its longest palindromic subsequence length*/
        return n - k;
    }
}

// Create an instance of Solution class
const sol = new Solution();

// Call minInsertion function and print the result
const s = "abcaa";
console.log("The Minimum insertions required to make string palindrome: " + sol.minInsertion(s));

Complexity Analysis:

Time Complexity: O(N*N), Where N is the length of the given string. As two nested loops are used to solve the problem.

Space Complexity: O(N), We are using an external array of size ‘N+1’ to store only two rows.

Problem List

Minimum insertions to make string palindrome

Examples:

Constraints

Hints

Company Tags

Editorial

Understanding:

Approach:

Complexity Analysis:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code