Find Number of Minimum Insertion to Make a String Palindrome

You have been given a string. You have to find out the number of minimum insertions to make this string palindrome. The string will contain only lower case alphabets.

Note:

What is a palindrome?

We call a string or a number palindrome, if it looks same from both front and behind. For example, the string “DAD” is a palindrome. So, from both side one can read the string same. Numbers like 121 is also palindrome.

Input:  “abcd”

Output:    3

Explanation: If we want to make the string palindrome then we have to add three characters. The palindrome string may be “abcdcba” (It is possible to build different sequence but the minimum number of insertions will be same i.e. 3).

Concept behind the solution

This problem can be solved by different approaches. We can use recursion for this solution. But this approach will take more time and space. So, we will use dynamic programming to solve this problem. If we use memorization then it can take more space for big input size. So, it is best to use tabulation approach.

Code:

// Program in C++ to find out the number of minimum insertions to make this string palindrome

#include <bits/stdc++.h>
using namespace std;
int my_fun(string s, int low, int high,vector<vector<int>>& dp)
{
	for(int i=1;i<=high;i++){
            for(int l=0,h=i;h<=high;h++,l++){
         if(s[l]==s[h]){
             dp[l][h]=dp[l+1][h-1];
        }
        else
             dp[l][h]=(min(dp[l+1][h],dp[l][h-1])+1);
        }
        }
        return dp[low][high]; 
}
// memorisation function 
/*int my_fun(string s, int low, int high,vector<vector<int>>& dp){
        if(dp[low][high]!=-1)
            return dp[low][high];
        else if(low==high)
            return 0;
        else if(low==high-1){
           if(s[low]==s[high])
                return 0;
            else 
                return 1;
        }
        else if(s[low]==s[high]){
            return dp[low][high]= my_fun (s,low+1,high-1,dp);
        }
        else
            return dp[low][high]=(min(my_fun (s,low,high-1,dp), my_fun (s,low+1,high,dp))+1);
    }*/
int main()
{
	string s = "abcd";
vector<int> x(s.size()+1,0);
        vector<vector<int>> dp(s.size()+1,x);
	cout << my_fun(s,0,s.size()-1,dp);
	return 0;
}

// Program in C to find out the number of minimum insertions to make this string palindrome

#include <stdio.h>
#include <string.h>
int min(int a, int b)
{ return a < b ? a : b; }
int my_fun(char str[], int n)
{
	int dp[n][n], l, h, i;
	memset(dp, 0, sizeof(dp));
	for (i = 1; i < n; ++i)
		for (l = 0, h = i; h < n; ++l, ++h)
			dp[l][h] = (str[l] == str[h])?
						dp[l+1][h-1] :
						(min(dp[l][h-1],
						dp[l+1][h]) + 1);
	return dp[0][n-1];
}
int main()
{
	char str[] = "abcd";
	printf("%d", my_fun(str, strlen(str)));
	return 0;
}

// Program in JAVA to find out the number of minimum insertions to make this string //palindrome

#include <stdio.h>
#include <string.h>
int min(int a, int b)
{ return a < b ? a : b; }
int my_fun(char str[], int n)
{
	int dp[n][n], l, h, i;
	memset(dp, 0, sizeof(dp));
	for (i = 1; i < n; ++i)
		for (l = 0, h = i; h < n; ++l, ++h)
			dp[l][h] = (str[l] == str[h])?
						dp[l+1][h-1] :
						(min(dp[l][h-1],
						dp[l+1][h]) + 1);
	return dp[0][n-1];
}
int main()
{
	char str[] = "abcd";
	printf("%d", my_fun(str, strlen(str)));
	return 0;
}

# Program in Python to find out the number of minimum insertions to make this string #palindrome

def Min(a, b):
	return min(a, b)
def my_fun(str1, n):
	dp = [[0 for i in range(n)]
				for i in range(n)]
	l, h, i = 0, 0, 0
	for i in range(1, n):
		l = 0
		for h in range(i, n):
			if str1[l] == str1[h]:
				dp[l][h] = dp[l + 1][h - 1]
			else:
				dp[l][h] = (Min(dp[l][h - 1],
								dp[l + 1][h]) + 1)
			l += 1
	return dp[0][n - 1];
str1 = "abcd"
print(my_fun(str1, len(str1)))

// Program in C# to find out the number of minimum insertions to make this string palindrome

using System;
class bn
{
	static int my_fun(char []str, int n)
	{
		int [,]dp = new int[n, n];
		int l, h, i;
		for (i = 1; i < n; ++i)
		for (l = 0, h = i; h < n; ++l, ++h)
			dp[l, h] = (str[l] == str[h])?
						dp[l+1, h-1] :
						(Math.Min(dp[l, h-1],
								dp[l+1, h]) + 1);
		return dp[0, n-1];
	}
	public static void Main()
	{
		String str = "abcd";
		Console.Write(
		my_fun(str.ToCharArray(), str.Length));
	}
}


<script>

// Program in JavaScript to find out the number of minimum insertions to make this //string  palindrome

function my_fun(str,n)
	{
		
		let dp=new Array(n);
		for(let i=0;i<n;i++)
		{
			dp[i]=new Array(n);
		}
				
		for(let i=0;i<n;i++)
		{
			for(let j=0;j<n;j++)
			{
				dp[i][j]=0;
			}
		}	
		
		let l=0, h=0, i=0;
		for (i = 1; i < n; i++)
		{
			for (l = 0, h = i; h < n; l++, h++)
			{
								
				dp[l][h] = (str[l] == str[h]) ? dp[l+1][h-1] : (Math.min(dp[l][h-1],dp[l+1][h]) + 1);
				
			}
		}
		return dp[0][n - 1];
	}
	let str = "abcd";
	document.write(my_fun(str, str.length));
	
	
</script>

Output: