Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

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

First, let’s start by looking at the brute force solution to solve this problem.

Java
class LPS
{ 
  public static 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.charAt(startIndex) == st.charAt(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 Math.max(c1, c2);
  }
  public static int LPSLength(String st) {
    return LPSLengthRec(st, 0, st.length() - 1);
  }
  public static void main(String args[]) 
  {
    System.out.println(LPSLength("cddpd"));
    System.out.println(LPSLength("abdbca"));
    System.out.println(LPSLength("cddpd"));
    System.out.println(LPSLength("pqr"));
  }
};

Explanation

In this brute force solution:

  1. If the element at the beginning and the end are the same, we increment the count by two and make a recursive call for the remaining sequence (lines 13-14).

  2. Otherwise, we skip the element either from the beginning or the end to make two recursive calls for the remaining subsequence (lines 17-18).

  3. After that, we return the greater result (line 19).

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

The brute force recursive solution results in redundant recursive calls. We can try and memoize the code to reduce the number of same recursive calls.

Let’s take a look at how this can be ...