Trusted answers to developer questions
Trusted Answers to Developer Questions

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() 
{ 
    string original = "ABBCAD"; 
    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++
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring