Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Problem Statement
3.
Recursive Approach
3.1.
Algorithm
3.2.
Program in C++
3.3.
Program in Python
3.4.
Program in Java
3.5.
Complexity Analysis
4.
Dynamic Programming Approach
4.1.
Algorithm
4.2.
Program in C++
4.3.
Program in Python
4.4.
Program in Java
4.5.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is a palindrome?
5.2.
What is the difference between a subsequence and a substring?
5.3.
What is the Time Complexity of the Recursive Approach for the Minimum Insertions to make a palindrome problem?
6.
Conclusion
6.1.
Recommended Problems:
6.2.
Recommended Readings based on Palindrome:
Last Updated: Mar 27, 2024
Medium

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

Author Ujjawal Gupta
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

One day, Ninja’s teacher gave him an assignment in which he had to find the minimum insertions in the given string to make it a palindrome. Help ninja to pass the assignment.

The above problem is the standard dynamic programming problem. Dynamic programming based-coding problems are widely asked in coding contests and various coding interviews.

This blog will solve the above problem using a dynamic programming approach.

The Problem Statement

Depiction of what is Palindrome

You have a string ‘S’ consisting of only lowercase characters. Your task is to find the minimum insertions in ‘S’ to make it a palindromic string.

Note: You can insert any number of lowercase characters anywhere in the string.

For example,

  • In “a”, the number of insertions required is 0 as string is already in palindrome.
  • In “ab”, the number of insertions required is 1 to make it a palindromic string. There are two ways to do it “aba”, “bab”.
  • In “bad”, the number of insertions required is 2 to make it a palindromic string. One of the possible palindromic strings formed is “badab”.
     

Recommended: Try the Problem yourself before moving on to the solution.
(Also See: Data Structures)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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 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;
}

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))

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);
        }
    }
   
}

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(2N) 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(2N)

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:

Recommended Readings based on Palindrome:

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!

Previous article
Minimum Characters Require to Remove from Binary String to Sort it in Ascending Order
Next article
Minimize Cost to Convert all ‘0’s to ‘1’s with Cost of Converting ‘0’s Group be K and that of ‘1’ be K / 3
Live masterclass