Algorithms for Coding Interviews in C++/

...

/

Solution: Longest Palindromic Subsequence

Solution: Longest Palindromic Subsequence

This review provides a detailed analysis of the different ways to solve the Longest Palindromic Subsequence Problem

We'll cover the following...

Solution #1: Brute Force

Press + to interact
#include <iostream>
#include <string>
using namespace std;
int LPSLengthRec(string st, int startIndex, int endIndex) {
  if (startIndex > endIndex)
    return 0;
  // every sequence with one element is a palindrome of length 1
  if (startIndex == endIndex)
    return 1;
  // case 1: elements at the beginning and the end are the same
  if (st[startIndex] == st[endIndex])
    return 2 + LPSLengthRec(st, startIndex + 1, endIndex - 1);
  // case 2: skip one element either from the beginning or the end
  int c1 = LPSLengthRec(st, startIndex + 1, endIndex);
  int c2 = LPSLengthRec(st, startIndex, endIndex - 1);
  return max(c1, c2);
}
int LPSLength(string st) {
  return LPSLengthRec(st, 0, st.length() - 1);
}
int main() {
  cout << LPSLength("cddpd") << endl;
  cout << LPSLength("abdbca") << endl;
  cout << LPSLength("cddpd") << endl;
  cout << LPSLength("pqr") << endl;
}

By now, you must have noticed a pattern in the way we approach dynamic programming problems.

In this brute force solution,

  1. If the element at the beginning and the end are the same, we increment our count by two and make a recursive call for the remaining sequence.
  2. Otherwise, we will skip the element either from the beginning or the end to make two recursive calls for the remaining subsequence. After that, we return the greater result.

Time Complexity

The time complexity of the above algorithm is exponential O(2n)O(2^n), where n is the length of the input sequence. The space complexity is O(n)O(n) which is the maximum number of times that the function is called, so this is the space used to store the recursion stack.

Solution #2: Memoization

Press + to interact
#include <iostream>
#include <vector>
using namespace std;
int LPSLengthRec(vector< vector<int> > lookupTable, string st, int startIndex, int endIndex) {
    if(startIndex > endIndex)
      return 0;
    // every sequence with one element is a palindrome of length 1
    if(startIndex == endIndex)
      return 1;
  
    if(lookupTable[startIndex][endIndex] == 0) {
      // case 1: elements at the beginning and the end are the same
      if(st[startIndex] == st[endIndex]) {
        lookupTable[startIndex][endIndex] = 2 + LPSLengthRec(lookupTable, st, startIndex+1, endIndex-1);
      } else {
        // case 2: skip one element either from the beginning or the end
        int c1 =  LPSLengthRec(lookupTable, st, startIndex+1, endIndex);
        int c2 =  LPSLengthRec(lookupTable, st, startIndex, endIndex-1);
        lookupTable[startIndex][endIndex] = max(c1, c2);
      }
    }
    return lookupTable[startIndex][endIndex];
}
int LPSLength(string st) {
// Initializing a lookup table of dimensions st.length() x st.length()
  vector< vector<int> > lookupTable(
   st.length(),
   vector<int>(st.length(), 0));
  return LPSLengthRec(lookupTable, st, 0, st.length()-1);
}
int main() {
  cout << LPSLength("cddpd") << endl;
  cout << LPSLength("abdbca") << endl;
  cout << LPSLength("cddpd") << endl;
  cout << LPSLength("pqr") << endl;
}

As done is memoization, we use an ...