Find the Minimum Insertions in the Given String to Form a Palindrome

Recursive Approach

For finding minimum insertions in a string, we have two possibilities. The first possibility is that the value of starting index ‘START’ and ending index ‘END’ of the string is equal then our problem is reduced to the smaller problem of finding the minimum insertions in the string starting from ‘START + 1’ and ending at ‘END - 1’.

The second possibility is that the value of starting index ‘START’ and ending index ‘END’ of the string is not equal then we have two cases:

• Either insert the first character at the end of the string. In this case, our problem is reduced to the smaller problem of finding the minimum insertions required in the string starting from ‘START + 1’ and ending at ‘END’.
• Insert the last character at the start of the string. In this case, our problem is reduced to the smaller problem of finding the minimum insertions required in the string starting from ‘START’ and ending at ‘END - 1’. 

Since we can solve the problem by breaking it into smaller problems of the same type, the above problem can be solved using Recursion. Simply create a function, minInsertion(S) which will call minInsertionHelper(S, START, END), where ‘START’ and ‘END’ are the starting and ending indices of string ‘S’, and the function returns the minimum number of insertions required to make the substring of ‘S’ (starting from ‘START’ and ending on ‘END’) palindrome.

Algorithm

The algorithm for the recursive (see Recursion) approach is as follows:

• Define the function minInsertionHelper(S, START, END):
  • Function description:
    • It takes three parameters, i.e., the string ‘S’, starting index ‘START’, and ending index ‘END’.
    • The function returns the answer for substring starting from ‘START’ to ‘END’.
  • Working:
  • If START  > END:
    Return 0.
  • If START ==  END:
    Return 0.
  • If S[START] == S[END]:
    Return minInsertionHelper(S, START + 1, END - 1).
  • Else:
    Return min(minInsertionHelper(S, START + 1, END), minInsertionHelper(S, START, END - 1)).
• Call minInsertionHeper(S, 0, S.LENGTH - 1) from minInsertion().

Program in C++

#include <iostream>
using namespace std;

// Recursive Helper Function.
int minInsertionHelper(string &s, int start, int end)
{

    // Base conditions to terminate the recursive call.
    if (start > end)
        return 0;
    if (start == end)
        return 0;

    // If starting and ending index have same value.
    if (s[start] == s[end])
    {
        return minInsertionHelper(s, start + 1, end - 1);
    }
    else
    {
        return min(minInsertionHelper(s, start + 1, end), minInsertionHelper(s, start, end - 1)) + 1;
    }
}

// Function to calculate minimum number of insertions required for given string to be a palindrome.
int minInsertion(string &s) {
    return minInsertionHelper(s, 0, s.length() - 1);
}

int main()
{
    // Taking string as an input.
    string s;
    cin >> s;

    // Call function.
    int ans = minInsertion(s);

    // Print the final answer.
    cout << ans;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Program in Python

import sys
# Finding the minimum number of insertions using recursion
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 result of the comparison
   # subproblem(s) will be called.
    
   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 (main function)
if __name__ == "__main__":
    
   str =input()
   print(findMinInsertions(str, 0, len(str) - 1))

You can also try this code with Online Python Compiler

Run Code

You can also read about Palindrome Number in Python here.

Program in Java

import java.util.Scanner;

public class MinInsertion {
    static int minInsertionHelper(char s[], int start, int end)
    {

    // Base conditions to terminate the recursive call.
        if (start > end)
            return 0;
        if (start == end)
            return 0;

        // If starting and ending index have same value.
        if (s[start] == s[end])
        {
            return minInsertionHelper(s, start + 1, end - 1);
        }
        else
        {
            return Math.min(minInsertionHelper(s, start + 1, end), minInsertionHelper(s, start, end - 1)) + 1;
        }
    }



    // Function to calculate minimum number of insertions required for given string to be a palindrome.
    static int minInsertion(char s[]) {
        return minInsertionHelper(s, 0, s.length - 1);
    }
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            char[] str= sc.next().toCharArray();    
            // Call function.
            int ans = minInsertion(str);
            System.out.println(ans);
            // Print the final answer.
        }
    }
}

Input

ab

Output

1

Complexity Analysis

Time Complexity

O(2 ^ N), where 'N' is the length of the string.

In the worst case, at every call, we will be calling two additional recursive calls. Hence, its time complexity is O(2^N).

Space Complexity

O(N), where ‘N’ is the size of the string.

Recursive stack takes O(N) extra space.

Also check out - Substr C++

Also Read - Strong number in c

Dynamic Programming Approach

The above problem can be solved by finding the longest common subsequence of ‘S’ and the reverse of ‘S‘, with the final count of insertion being the count of remaining characters to balance each character we need to insert that character at the appropriate place. This can be easily understood by taking an example: 

For example, ‘S’ = “abccd”, the reverse string of ‘S’ is “dccba”. The longest common subsequence of both the string is “cc”. So, we need to insert all the other characters except “cc” to form a palindrome. The final string made after insertion is “dabccbad”. Hence total insertion required is 3.

We can find LCS of string using dynamic programming. Here, dynamic programming is used to calculate the length of the longest common subsequence of ‘S’ and the reverse of ‘S’. The final answer will be the difference between the size of string ‘S’ and the length of the longest common subsequence.

Algorithm

The algorithm of the dynamic programming approach is as follows:

• Define the function longestCommonSubsequence(s,r):
  • Function Description:
    • It takes two parameters, i.e., strings ‘S’ and ‘R’.
    • This function returns the length of the longest common subsequence of ‘S’ and ‘R’.
  • Working:
    • Create 2-dimensional array DP[S.LENGTH()+1][R.LENGTH()+1].
    • Iterate loop for i = 0 to i < = S.LENGTH():
    • Iterate loop for j = 0 to j <= R.LENGTH():
      • If i == 0 or j == 0:
      • DP[i][j] = 0.
      • Else if S[i - 1] == R[j - 1]:
      • DP[i][j] = DP[i - 1][j - 1] + 1.
      • Else:
      • DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
    • Return DP[S.SIZE()][R.SIZE()].
• Define a function minInsertion(S):
  • Function Description:
    • It takes string ‘S’ as a parameter.
    • It returns the minimum count of insertions required.
  • Working:
    • String R = S.
    • Reverse the string ‘R’.
    • MAX_LEN = longestCommonSubsequence(S , R).
    • Return S.LENGTH() - MAX_LEN.
• Call the minInsertion(S).

Program in C++

#include <iostream>
#include <algorithm>
using namespace std;

// Function to find LCS of string ‘S’ and ‘R’.
int longestCommonSubsequence(string s, string r)
{

    // Creating 2-dimensional ‘DP’ array to store the result.
    int dp[s.length() + 1][r.length() + 1];
    for (int i = 0; i <= s.size(); i++)
    {
        for (int j = 0; j <= r.size(); j++)
        {
            if (i == 0 || j == 0)
                dp[i][j] = 0;

            else if (s[i - 1] == r[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;

            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[s.length()][r.length()];
}

int minInsertion(string s){
   // Creating a string to store the reverse of string ‘S’.
    string r = s;
    reverse(r.begin(), r.end());

    // Call function.
    int maxlen = longestCommonSubsequence(s, r);

    // Print answer.
    return s.length() - maxlen;
}

int main()
{
    // Taking string as an input.
    string s;
    cin >> s;
    // Calling ‘minInsertion()’ function.
    int ans = minimumInsertions(s);

    // Print answer.
    cout << ans;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Program in Python

# A DP function to find minimum number of insertions
def minInsertions(s):
   s1=s
   s2=s[::-1]
   if s1==s2:
       return 0
   m=n=len(s)
   
   # Create a table of size n*n. dp[i][j] will store 
   # minimum number of insertions
   # required to convert str[i..j] to a palindrome.
   dp=[[-1 for i in range(n+1)]for i in range(m+1)]
   dp[0]=[0]*(n+1)
   for i in range(m+1):
       dp[i][0]=0
       
   for i in range(1,m+1):
       for j in range(1,n+1):
           if s1[i-1]==s2[j-1]:
               dp[i][j]=dp[i-1][j-1]+1
           else:
               dp[i][j]=max(dp[i-1][j],dp[i][j-1])
   return m-dp[-1][-1]
   
#Driver code (main function)
if __name__ == "__main__":
   str = input() #input string that needs to be checked
   print(minInsertions(str))

You can also try this code with Online Python Compiler

Run Code

Program in Java

import java.util.Scanner;

public class MinInsertion {
    // Function to find LCS of string ‘S’ and ‘R’.
    static int longestCommonSubsequence(char s[], char r[]){
        int n=s.length, m=r.length;
        int[][] dp = new int[n+1][m+1];
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(i==0 || j==0){
                    dp[i][j]=0;
                }else if(s[i-1]==r[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
            
        }
        return dp[n][m];
    }
    
    static int minimumInsertions(char s[]){
        char[] r=new char[s.length];
        int j=0;
        for(int i=s.length-1;i>=0;i--){
            r[j]=s[i];
            j++;
        }
        
        int maxlen = longestCommonSubsequence(s, r);
        return s.length - maxlen;
    }
    
    public static void main(String[] args){
        try(Scanner sc = new Scanner(System.in)){
            char[] s=sc.next().toCharArray();
            int ans=minimumInsertions(s);
            System.out.println(ans);
        }
    }
   
}

You can also try this code with Online Java Compiler

Run Code

Input

abbc

Output

2

Complexity Analysis

Time Complexity

O(N^2), where ‘N’ is the size of the string.

Iterating a loop inside another loop takes N^2 time.

Space Complexity

O(N^2), where ‘N’ is the size of the string.

Creating a 2-dimensional array takes (N^2) space. 

Also check out - Rod Cutting Problem

Check out Longest Common Substring

Frequently Asked Questions

What is a palindrome?

A palindrome is a string that reads the same in left-right as well as right-left traversal i.e., the reverse of the string is the same as the original string for eg. “aba”.

What is the difference between a subsequence and a substring?

In a subsequence, the considered characters of a string may or may not be consecutive. However, in a substring, all the involved characters have to be consecutive in nature.

What is the Time Complexity of the Recursive Approach for the Minimum Insertions to make a palindrome problem?

The Time Complexity of the recursive approach is O(2^N) where N is the length of the string. This is so because each character in the string is considered individually as to whether there would be an insertion required against it to make the string a palindrome. Thus there being two possible outcomes it is quite simple to determine that the time complexity of the recursive solution is O(2^N)

Conclusion

In this blog, we discussed how to make any string into a palindrome by minimum insertions of characters. We discussed two approaches to the solution one recursive (brute force) and on optimizing this approach we found an optimal approach using dynamic programming. Multiple solutions help us to inculcate curiosity and also increase our power of intuition.

Hence learning never stops, and there is a lot more to learn.

Recommended Problems:

• Longest Palindromic Subsequence
• Minimum Insertions
• Make Palindrome
• Minimum Characters for Palindrome
• Top Dynamic Programming Questions

Recommended Readings based on Palindrome:

• Check If a String is a Palindrome
• How to Find all the Palindromic Partitions of a String
• Length of the Most Extended Palindrome List in a Linked List using O(1) Extra Space
• Palindrome Pattern
• Last Palindromic Date
• Check if a Linked List is Palindrome or not?
• Reverse A String In C
• Palindrome string

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and explore some of the Guided Paths on topics such as Data Structures and Algorithms brought to you by leading industry experts. Till then, Happy Coding!