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 2dimensional 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 2dimensional ‘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[i1]==s2[j1]:
dp[i][j]=dp[i1][j1]+1
else:
dp[i][j]=max(dp[i1][j],dp[i][j1])
return mdp[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[i1]==r[j1]){
dp[i][j]=dp[i1][j1]+1;
}else{
dp[i][j]=Math.max(dp[i1][j], dp[i][j1]);
}
}
}
return dp[n][m];
}
static int minimumInsertions(char s[]){
char[] r=new char[s.length];
int j=0;
for(int i=s.length1;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 2dimensional 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 leftright as well as rightleft 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:
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!