Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Longest Palindromic Subsequence

Understand how to solve the longest palindromic subsequence problem using dynamic programming techniques. Learn brute force recursion, optimize with memoization to reduce time complexity, and apply bottom-up tabular methods for efficient solutions. This lesson equips you with the skills to analyze complexity and implement these algorithms in C++ coding interviews.

We'll cover the following...

Solution #1: Brute Force

C++
#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

C++
#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 ...