The Longest Palindromic Subsequence (LPS) problem is the problem of finding the longest subsequences of a string that is also a palindrome.

*The problem differs from problem of finding common substrings. Unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.*

For example, Consider the sequence ABBDCACB

The length of Longest Palindromic Subsequence is 5

The Longest Palindromic Subsequence is BCACB

The idea is to use recursion to solve this problem. The idea is compare the last character of the string X[i..j] with its first character. There are two possibilities –

2. If last character of string is different from the first character, we return maximum of the two values we get by

- removing the last character and recursing for the remaining substring X[i, j-1]
- removing the first character and recursing for the remaining substring X[i+1, j]

This yields the below recursive relation to find the length of longest repeated Subsequence of a sequence X.

| 1 (if i = j)

LPS[i..j] = | LPS[i+1..j-1] + 2 (if X[i] = X[j])

| max (LPS[i+1..j], LPS[i..j-1]) (if X[i] != X[j])

Below solution finds the length of longest repeated Subsequence of sequence X recursively by using above relations.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> using namespace std; // Function to find the length of Longest Palindromic Subsequence // of substring X[i..j] int longestPalindrome(string X, int i, int j) { // base condition if (i > j) return 0; // if string X has only one character, it is palindrome if (i == j) return 1; // if last character of the string is same as the first character if (X[i] == X[j]) // include first and last characters in palindrome // and recuse for the remaining substring X[i+1, j-1] return longestPalindrome(X, i + 1, j - 1) + 2; // if last character of string is different to the first character // 1. Remove last character and recurse for the remaining // substring X[i, j-1] // 2. Remove first character and recurse for the remaining // substring X[i+1, j] // return maximum of the two values return max (longestPalindrome(X, i, j - 1), longestPalindrome(X, i + 1, j)); } // main method int main() { string X = "ABBDCACB"; int n = X.length(); cout << "The length of Longest Palindromic Subsequence is " << longestPalindrome(X, 0, n - 1); return 0; } |

**Output: **

The length of Longest Palindromic Subsequence is 5

The worst case time complexity of above solution is exponential O(2^{n}) and auxiliary space used by the program is O(1). The worst case happens when there is no repeated character present in X (i.e. LPS length is 1) and each recursive call will end up in two recursive calls.

The LPS problem has an **optimal substructure**. We have seen that the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. The LPS problem also exhibits **overlapping subproblems** we will end up solving the same subproblem over and over again. Let us consider recursion tree for sequence of length 6 having all distinct characters (say ABCDEF) whose LPS length is 1.

As we can see, the same sub-problems (highlighted in same color) are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are *Memo*ized rather than computed again and again. This method is illustrated below –

**Memoized C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <unordered_map> using namespace std; // Function to find the length of Longest Palindromic Subsequence // of substring X[i..j] int longestPalindrome(string X, int i, int j, auto &lookup) { // base condition if (i > j) return 0; // if string X has only one character, it is palindrome if (i == j) return 1; // construct a unique map key from dynamic elements of the input string key = to_string(i) + "|" + to_string(j); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // if last character of the string is same as the first character // include first and last characters in palindrome and recuse // for the remaining substring X[i+1, j-1] if (X[i] == X[j]) lookup[key] = longestPalindrome(X, i + 1, j - 1, lookup) + 2; else // if last character of string is different to the first character // 1. Remove last char and recurse for the remaining // substring X[i, j-1] // 2. Remove first char and recurse for the remaining // substring X[i+1, j] // return maximum of the two values lookup[key] = max (longestPalindrome(X, i, j - 1, lookup), longestPalindrome(X, i + 1, j, lookup)); } // return the subproblem solution from the map return lookup[key]; } int main() { string X = "ABBDCACB"; int n = X.length(); // create a map to store solutions of subproblems unordered_map<string, int> lookup; cout << "The length of Longest Palindromic Subsequence is " << longestPalindrome(X, 0, n - 1, lookup); return 0; } |

**Output: **

The length of Longest Palindromic Subsequence is 5

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n^{2}).

Above solutions only find the length of Longest Palindromic Subsequence but do not print the Longest Palindromic Subsequence itself.

**How can we print Longest Palindromic Subsequence?**

The Longest Palindromic Subsequence problem is classic variation of Longest Common Subsequence (LCS) problem. The idea is to find LCS of given string with its reverse i.e. call LCS(X, reverse(X)) and the Longest Common Subsequence will be Longest Palindromic Subsequence.

We recommend to go through below posts before continuing –

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <bits/stdc++.h> using namespace std; #define N 25 // lookup[i][j] stores the length of LCS of substring X[0..i-1], Y[0..j-1] int lookup[N][N]; // Function to find LCS of string X[0..m-1] and Y[0..n-1] string longestPalindrome(string X, string Y, int m, int n) { // return empty string if we have reached the end of // either sequence if (m == 0 || n == 0) return string(""); // if last character of X and Y matches if (X[m - 1] == Y[n - 1]) { // append current character (X[m-1] or Y[n-1]) to LCS of // substring X[0..m-2] and Y[0..n-2] return longestPalindrome(X, Y, m - 1, n - 1) + X[m - 1]; } // else when the last character of X and Y are different // if top cell of current cell has more value than the left // cell, then drop current character of string X and find LCS // of substring X[0..m-2], Y[0..n-1] if (lookup[m - 1][n] > lookup[m][n - 1]) return longestPalindrome(X, Y, m - 1, n); // if left cell of current cell has more value than the top // cell, then drop current character of string Y and find LCS // of substring X[0..m-1], Y[0..n-2] return longestPalindrome(X, Y, m, n - 1); } // Function to find length of LCS of substring X[0..n-1] and Y[0..n-1] int LCSLength(string X, string Y, int n) { // first row and first column of the lookup table // are already 0 as lookup[][] is globally declared // fill the lookup table in bottom-up manner for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // if current character of X and Y matches if (X[i - 1] == Y[j - 1]) lookup[i][j] = lookup[i - 1][j - 1] + 1; // else if current character of X and Y don't match else lookup[i][j] = max(lookup[i - 1][j], lookup[i][j - 1]); } } return lookup[n][n]; } // main function int main() { string X = "ABBDCACB"; int m = X.length(); // string Y is reverse of X string Y = X; reverse(Y.begin(), Y.end()); // Find length of Longest Palindromic Subsequence using LCS cout << "The length of Longest Palindromic Subsequence is " << LCSLength(X, Y, m) << endl; // Print Longest Palindromic Subsequence using lookup table cout << "The Longest Palindromic Subsequence is " << longestPalindrome(X, Y, m, m); return 0; } |

**Output: **

The length of Longest Palindromic Subsequence is 5

The Longest Palindromic Subsequence is BCACB

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n^{2}).

**Exercise:** Write bottom-up solution for above recursive top-down version.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂