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) ...

Access this course and 1400+ top-rated courses and projects.