Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Longest Palindromic Subsequence

Problem Statement

Given a sequence, find the length of its Longest Palindromic Subsequence (LPS). In a palindromic subsequence, elements read the same backward and forward.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: "abdbca"
Output: 5
Explanation: LPS is "abdba".

Example 2:

Input: = "cddpd"
Output: 3
Explanation: LPS is "ddd".

Example 3:

Input: = "pqr"
Output: 1

.....

.....

.....

Like the course? Get enrolled and start learning!
Leandro Casuso

Leandro Casuso

· 6 days ago

We could improve the DP solution using the common approach of maintaining only the last needed rows (or diagonals if you use them instead of the rows). That will reduce the space to O(N).

S

singhursefamily

· a year ago

The two dynamic programming solutions have time and space complexity both of O(N^2).

I found a solution that also has a time complexity of O(N^2) but reduces the space complexity to O(1). It uses a two pointer approach. The code in in Javascript.

findLPSLength(str) {
    // two pointers, one on each end of `str`
    let left = 0;
    let right = str.length - 1;
    
    // size of the palindrome. this is the function output.
    let size = 0;

    while (left < right) {
      const target = str[left];
      let r;

      for (r = right; r > left; r -= 1) {
        const consider = str[r];
        if (target === consider) {
          size += 2;
          break;
        }
      }

      // move right pointer only if a match was found.
      // (r will be greater than left
Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLPSLength(self, st):
    
    def is_palindrom(s):
      i = 0
      j = len(s) - 1
      while i <= j:
        if s[i] != s[j]:
          return False
        i += 1
        j -= 1
      return True
    
    def dp(index, s, memo):
      if s in memo:
        return memo[s]

      if is_palindrom(s):       
        return len(s)

      if index >= len(s):
        return 0

      skip_char = dp(index + 1, s[:], memo)

      with_char = dp(index + 1, s[:index] + s[index+1:], memo)

      result = max(skip_char, with_char)

      memo[s] = result
      
      return result

    return dp(0, st, {})
Show 1 reply
G

Gary

· 4 years ago

Why does the bottom up solution here start with startIndex at n - 1 instead of 0, like in the Longest Common Substring/Subsequence problems in chapter 6?

Show 1 reply
M

Mircea C

· 5 years ago

For the memoisation tecgnique, isn’t the time complexity still 2^n? We still have 2^n function calls...

Show 1 reply

Reading Progress

0%

Vote for new content