Related Tags

subsequence
algorithm
lps
c++

# Implementing the longest palindromic subsequence algorithm in C++ Educative Answers Team

The longest palindromic subsequence is the longest sequence of characters in a string that is spelled the same forward as it is backward.

A subsequence differs from a substring since characters in a subsequence are not required to be at consecutive positions in the original string.

Before proceeding further, read up on the thought process for the algorithm here.

## Dry run

Let’s use the string “ABBCAD” as the example on which to dry run the LPS algorithm.

Consider the following slideshow that visualizes how the memo is created ​and filled with values:

1 of 20

## Code

The code below implements the LPS algorithm in C++:

#include <iostream>
#include <algorithm> // to use reverse() function

using namespace std;

// LCS is used to find the LPS of a string:
// just find the LCS of the original and reversed string
// to get the LPS.
string LCS(string original, string reversed)
{
int m = original.length(), n = reversed.length();

int memo[m+1][n+1]; // create a 2D array to serve as a memo

// Populate the memo using the mathematical equation for LCS.
// Note that a cell, memo[i][j], denotes the
// length of LCS/LPS of original[0..i-1] and reversed[0..j-1].
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
memo[i][j] = 0;
else if (original[i-1] == reversed[j-1])
memo[i][j] = memo[i-1][j-1] + 1;
else
memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
}
}

// create an empty string to store the LPS.
string LPS = "";

// Start backtracking from the right-bottom most
// cell of the memo.
int i = m, j = n;
while (i > 0 && j > 0)
{
// if the current character of original and
// reversed are the same, then that character is
// a part of the LPS. Move diagonally to the top-left
// cell in this case.
if (original[i-1] == reversed[j-1])
{
LPS += original[i-1];
i--;
j--;
}
// If not same, then find the larger of
// two and go in the direction of larger
// valued cell.
else if (memo[i-1][j] > memo[i][j-1])
i--;
else
j--;
}
return LPS;
}

// driver code
int main()
{
cout << "Original string is: " << original << endl;
string reversed = original;
reverse(reversed.begin(), reversed.end());
cout << "Longest Palindromic Subsequence is: " <<
LCS(original, reversed) << endl;
return 0;
} 

RELATED TAGS

subsequence
algorithm
lps
c++ 