C Program to Find Minimum Insertions to Form a Palindrome

A palindrome is a string that is just equal to the reverse of it. We are given a string and we have to find the minimum number of insertions of any characters required to make the given string as the palindrome. We will see the three approaches: first recursive approach, then we will memorize this solution, and last, we will implement the dynamic programming approach.

Recursive Approach

Example

#include <stdio.h> // library for input and output #include <limits.h> // library to get the integer limits #include <string.h> // library for strings // function to find the minimum of two number // as it is not present in the c language int findMin(int a, int b){ if(a < b){ return a; } else{ return b; } } // creating the function to find the required answer we will make recursive calls to it int findAns(char str[], int start, int end){ // base condition if (start > end){ return INT_MAX; } else if(start == end){ return 0; } else if (start == end - 1){ if(str[start] == str[end]){ return 0; } else return 1; } // check if both start and end characters are the same make callson the basis of that if(str[start] == str[end]){ return findAns(str,start+1, end-1); } else{ return 1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end)); } } // main function int main(){ char str[] = "thisisthestring"; // given string printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1)); return 0; } 

Output

The minimum number of insertions required to form the palindrome is: 8

Time and Space Complexity

The time complexity of the above code is O(2^N), as we are making choice for each insertion, where N is the size of the given string.

The space complexity of the above code is O(N), that is used in the recursive calls.

Memorization Approach

Example

#include <stdio.h> // library for input and output #include <limits.h> // library to get the integer limits #include <string.h> // library for strings int memo[1005][1005]; // array to store the recursion results // function to find the minimum of two number // as it is not present in the c language int findMin(int a, int b){ if(a < b){ return a; } else{ return b; } } // creating the function to find the required answer we will make recursive calls to it int findAns(char str[], int start, int end){ // base condition if (start > end){ return INT_MAX; } else if(start == end){ return 0; } else if (start == end - 1){ if(str[start] == str[end]){ return 0; } else return 1; } // if already have the result if(memo[start][end] != -1){ return memo[start][end]; } // check if both start and end characters are same make calls on basis of that if(str[start] == str[end]){ memo[start][end] = findAns(str,start+1, end-1); } else{ memo[start][end] = 1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end)); } return memo[start][end]; } int main(){ char str[] = "thisisthestring"; // given string //Initializing the memo array memset(memo,-1,sizeof(memo)); printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1)); return 0; } 

Output

The minimum number of insertions required to form the palindrome is: 8

Time and Space Complexity

The time complexity of the above code is O(N^2), as we are storing the results that are already calculated.

The space complexity of the above code is O(N^2), because we have used the extra space here.

Dynamic Programming Approach

Example

#include <stdio.h> // library for input and output #include <limits.h> // library to get the integer limits #include <string.h> // library for strings // function to find the minimum of two number // as it is not present in the c language int findMin(int a, int b){ if(a < b){ return a; } else{ return b; } } // creating a function to find the required answer int findAns(char str[], int len){ // creating the table and initialzing it int memo[1005][1005]; memset(memo,0,sizeof(memo)); // filling the table by traversing over the string for (int i = 1; i < len; i++){ for (int start= 0, end = i; end < len; start++, end++){ if(str[start] == str[end]){ memo[start][end] = memo[start+1][end-1]; } else{ memo[start][end] = 1 + findMin(memo[start][end-1], memo[start+1][end]); } } } // return the minimum numbers of interstion required for the complete string return memo[0][len-1]; } int main(){ char str[] = "thisisthestring"; // given string // calling to the function printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str, strlen(str))); return 0; } 

Output

The minimum number of insertions required to form the palindrome is: 8

Time and Space Complexity

The time complexity of the above code is O(N^2), as we are using the nested for loops here.

The space complexity of the above code is O(N^2), because we have used the extra space here.

Conclusion

In this tutorial, we have implemented three approaches to find the number of minimum insertions required to make the given string a palindrome. We have implemented a recursive approach and then memorized it. In the end, we have implemented the tabulation approach or the dynamic programming approach.