Longest Palindromic Subsequence Problem

This is a C++ Program that Solves Longest Palindromic Subsequence Problem using Dynamic Programming technique.

Problem Description

You are given a string str. Find the length of longest palindromic subsequence in the given string.

Problem Solution

This problem is a variation of the longest common subsequence problem. The required result is simply the LCS of the given string and its reversed string.

Expected Input and Output

Case-1:

str= ADBDCA
result = 5 (ADBDA)

Program/Source Code

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

```
#include<iostream>
```
```
#include<string>
```
```
#include<algorithm>
```
```
 
```
```
using namespace std;
```
```
 
```

int longestCommonSubsequece(string str1, string str2)

```
{
```

    int len1=str1.length(), len2=str2.length();

```
    int i, j;
```
```
 
```

    //create a matrix of order (len1+1)*(len2+1) to tabulate values

```
    int LCS[len1+1][len2+1];
```
```
 
```

    //LCS[i][j]=Length of longest common subsequence of str1[0....(i-1)] and str2[0...(j-1)]

```
 
```
```
    //initializing
```
```
    for(i=0;i<=len1;i++)
```
```
        LCS[i][0]=0;    //empty str2
```
```
 
```
```
    for(j=0;j<=len2;j++)
```
```
        LCS[0][j]=0;   //empty str1
```
```
 
```

    //now, start filling the matrix row wise

```
    for(i=1;i<=len1;i++)
```
```
    {
```
```
        for(j=1;j<=len2;j++)
```
```
        {
```

            //if current character of both strings match

```
            if(str1[i-1]==str2[j-1])
```
```
            {
```

                LCS[i][j]=1+LCS[i-1][j-1];

```
            }
```
```
 
```
```
            //mismatch
```
```
            else
```
```
            {
```

                LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]);

```
            }
```
```
        }
```
```
    }
```
```
 
```
```
    //now, return the final value 
```
```
    return LCS[len1][len2];
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    string str1;
```
```
 
```
```
    cout<<"Enter the string - ";
```
```
    getline(cin,str1);
```
```
 
```
```
    string str2=str1;
```
```
    reverse(str2.begin(),str2.end());
```
```
 
```

    cout<<"Longest palindromic subsequence in the input string "<<endl;

    cout<<longestCommonSubsequece(str1,str2);

```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we will take input for str1. We will pass this string and its reverse 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++ longest_palindromic_subsequence.cpp
$ ./a.out
Enter the string - ADBDCA
Longest palindromic subsequence in the input string 
5

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!

« Prev - Sum of Digits Problem using Dynamic Programming

» Next - Building Problem – Dynamic Programming Solutions

Related Posts:

Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Apply for Computer Science Internship
Check Programming Books

Recommended Articles: