Make Palindrome Problem – Dynamic Programming Solutions

This is a C++ Program that Solves Make Palindrome Problem using Dynamic Programming technique.

Problem Description

You are given a string str. Find the minimum number of characters to be inserted to string str to convert it to a palindrome.

Problem Solution

This problem is a variation of the longest common subsequence problem. First, find the LCS of the given string and its reverse. Then, the required result is simply the length of given string minus the calculated LCS.

Expected Input and Output

Case-1:

str= ABCDE
result = 4 (ABCDEDCBA)
Program/Source Code

Here is source code of the C++ Program to Solve Make Palindrome Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
advertisement
  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int longestCommonSubsequece(string str1, string str2)
  8. {
  9.     int len1=str1.length(), len2=str2.length();
  10.     int i, j;
  11.  
  12.     //create a matrix of order (len1+1)*(len2+1) to tabulate values
  13.     int LCS[len1+1][len2+1];
  14.  
  15.     //LCS[i][j]=Length of longest common subsequence of str1[0....(i-1)] and str2[0...(j-1)] 
  16.  
  17.     //initializing
  18.     for(i=0;i<=len1;i++)
  19.         LCS[i][0]=0;    //empty str2
  20.  
  21.     for(j=0;j<=len2;j++)
  22.         LCS[0][j]=0;   //empty str1
  23.  
  24.     //now, start filling the matrix row wise
  25.     for(i=1;i<=len1;i++)
  26.     {
  27.         for(j=1;j<=len2;j++)
  28.         {
  29.             //if current character of both strings match
  30.             if(str1[i-1]==str2[j-1])
  31.             {
  32.                 LCS[i][j]=1+LCS[i-1][j-1];
  33.             }
  34.  
  35.             //mismatch
  36.             else
  37.             {
  38.                 LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);
  39.             }
  40.         }
  41.     }
  42.  
  43.     //now, return the final value 
  44.     return LCS[len1][len2];
  45.  
  46. }
  47.  
  48. int main()
  49. {
  50.     string str1;
  51.  
  52.     cout<<"Enter the string - ";
  53.     getline(cin,str1);
  54.  
  55.     string str2=str1;
  56.     reverse(str2.begin(),str2.end());
  57.  
  58.     cout<<"Minimum number of characters to be inserted in the input string to make it a palindrome is "<<endl;
  59.     cout<<str1.length()-longestCommonSubsequece(str1,str2);
  60.  
  61.     cout<<endl;
  62.     return 0;
  63. }
Program Explanation

In the main function, we will take input for str1 and str2. We will pass these to the function longestCommonSubsequence as parameters. This function will calculate the result using bottom up DP and return the value which is displayed on the standard output.

Runtime Test Cases
 
Case-1:
$ g++ make_palindrome.cpp
$ ./a.out
Enter the string - abcde
Minimum number of characters to be inserted in the input string to make it a palindrome is 
4

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.