101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming Approach - Complex approach
  2. Space-Optimized Dynamic Programming - Complex approach
  3. Recursive Approach with Memoization - Complex approach

Approach 1: Dynamic Programming Approach

The key insight for solving this problem is to use dynamic programming. We'll define a 2D DP table where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j].

For each pair of indices (i, j), we have two cases:

  1. If the characters at positions i and j are the same, we can include them in our palindromic subsequence and look for the longest palindromic subsequence in the substring s[i+1...j-1].
  2. If the characters at positions i and j are different, we need to consider two options: either exclude the character at position i or exclude the character at position j, and take the maximum of these two options.

Algorithm:

  1. Create a 2D DP table of size n×n, where n is the length of the string.
  2. Initialize the diagonal elements dp[i][i] = 1, as a single character is always a palindrome of length 1.
  3. Fill the DP table diagonally, starting from substrings of length 2 and moving up to the full string.
  4. For each substring s[i...j]:
  5. a. If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] + 2.
  6. b. If s[i] != s[j], then dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  7. Return dp[0][n-1], which represents the length of the longest palindromic subsequence in the entire string.

Time Complexity:

O(n²)

Where n is the length of the string. We need to fill a 2D DP table of size n×n, and each cell takes constant time to compute.

Space Complexity:

O(n²)

We need a 2D DP table of size n×n to store the intermediate results.

Approach 2: Space-Optimized Dynamic Programming

We can optimize the space complexity of the dynamic programming approach by observing that to compute dp[i][j], we only need the values from the previous diagonal (dp[i+1][j-1]) and the current row and column (dp[i+1][j] and dp[i][j-1]).

This allows us to reduce the space complexity to O(n) by using two 1D arrays to store the current and previous rows of the DP table.

Algorithm:

  1. Create two 1D arrays, current and previous, of size n, where n is the length of the string.
  2. Initialize previous[i] = 1 for all i, as a single character is always a palindrome of length 1.
  3. For each diagonal d from 1 to n-1:
  4. a. For each i from 0 to n-d-1, calculate j = i+d.
  5. b. If s[i] == s[j], then current[i] = previous[i+1] + 2.
  6. c. If s[i] != s[j], then current[i] = max(current[i+1], previous[i]).
  7. d. After processing each diagonal, update previous = current and reset current.
  8. Return previous[0], which represents the length of the longest palindromic subsequence in the entire string.

Time Complexity:

O(n²)

The time complexity remains O(n²) as we still need to process all pairs of indices (i, j).

Space Complexity:

O(n)

We only need two 1D arrays of size n to store the current and previous rows of the DP table.

Approach 3: Recursive Approach with Memoization

Another approach is to use recursion with memoization. We can define a recursive function that computes the length of the longest palindromic subsequence for a given substring s[i...j].

To avoid redundant calculations, we'll use memoization to store the results of subproblems that we've already solved.

Algorithm:

  1. Create a memoization table memo of size n×n, initialized with -1.
  2. Define a recursive function LPS(i, j) that returns the length of the longest palindromic subsequence in the substring s[i...j]:
  3. a. If i > j, return 0.
  4. b. If i == j, return 1.
  5. c. If memo[i][j] != -1, return memo[i][j].
  6. d. If s[i] == s[j], then memo[i][j] = LPS(i+1, j-1) + 2.
  7. e. If s[i] != s[j], then memo[i][j] = max(LPS(i+1, j), LPS(i, j-1)).
  8. f. Return memo[i][j].
  9. Call LPS(0, n-1) to get the length of the longest palindromic subsequence in the entire string.

Time Complexity:

O(n²)

There are O(n²) possible subproblems, and each subproblem takes O(1) time to solve once we have the results of its subproblems.

Space Complexity:

O(n²)

We need a memoization table of size n×n to store the results of subproblems. The recursion stack also uses O(n) space in the worst case.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function longestPalindromeSubseq(s):
    n = length of s
    dp = 2D array of size n×n, initialized with 0s
 
    // Base case: single characters are palindromes of length 1
    for i from 0 to n-1:
        dp[i][i] = 1
 
    // Fill the DP table diagonally
    for len from 2 to n:
        for i from 0 to n-len:
            j = i + len - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
 
    return dp[0][n-1]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone