Code Implementation

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i+1][j-1]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]
      

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};
      

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = 2 + dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
      

var longestPalindromeSubseq = function(s) {
    const n = s.length;
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = 2 + dp[i + 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
};
      

Problem Description

Given a string s, you are to find the length of the longest subsequence of s that is also a palindrome. A subsequence means you can delete zero or more characters from s (without changing the order of the remaining characters) to form a new string. A palindrome is a string that reads the same forwards and backwards.

• You must return the length of the longest palindromic subsequence.
• You may not rearrange the characters; only deletion is allowed.
• All characters are lowercase or uppercase English letters.
• There is always at least one valid subsequence (at least any single character).

Example:
Input: s = "bbbab"
Output: 4
Explanation: The longest palindromic subsequence is "bbbb".

Thought Process

At first glance, it might seem like you could check every possible subsequence of s and see if it is a palindrome, then keep track of the longest one found. However, the number of possible subsequences grows exponentially with the length of the string, making this approach infeasible for larger strings.

To optimize, we notice that many subsequences overlap or share prefixes/suffixes. This suggests that we can use dynamic programming to store results of subproblems and reuse them. The key insight is that the problem can be broken down into smaller subproblems: for any substring, the answer depends on its first and last characters and the result for the substring in between.

By systematically building up solutions for small substrings and combining them, we can efficiently find the answer for the entire string.

Solution Approach

We use a dynamic programming approach. The main idea is to define a 2D array dp where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i..j].

• Base case: Any single character is a palindrome of length 1. So, for all i, set dp[i][i] = 1.
• Recurrence: For substring s[i..j]:
  • If s[i] == s[j], then those two characters can "wrap" a palindrome inside, so dp[i][j] = 2 + dp[i+1][j-1].
  • If s[i] != s[j], then the answer is the maximum between skipping either the first or the last character: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
• We fill the dp table from shorter substrings to longer ones, ensuring that when we compute dp[i][j], all the needed subproblems are already solved.
• The answer for the whole string will be in dp[0][n-1], where n is the length of s.

This approach avoids redundant calculations and efficiently solves the problem for any reasonable input size.

Example Walkthrough

Let's walk through the example s = "bbbab":

1. Initialize dp[i][i] = 1 for all i (each character alone is a palindrome).
2. Start filling dp for substrings of length 2 and up:
   • For i = 0, j = 1: s[0] == s[1] ('b' == 'b'), so dp[0][1] = 2.
   • For i = 1, j = 2: s[1] == s[2] ('b' == 'b'), so dp[1][2] = 2.
   • Continue for all substrings.
3. For the whole string i = 0, j = 4: s[0] == s[4] ('b' == 'b'), so dp[0][4] = 2 + dp[1][3].
4. dp[1][3] covers "bba", where the longest palindromic subsequence is "bb" (length 2), so dp[0][4] = 2 + 2 = 4.
5. The answer is 4, corresponding to the subsequence "bbbb".

Time and Space Complexity

• Brute-force approach: Tries all subsequences, of which there are 2^n. For each, checks if it's a palindrome (O(n)), so total time is O(n * 2^n), which is infeasible for large n.
• Dynamic programming approach:
  • There are O(n^2) substrings (all pairs (i, j) with i <= j).
  • Each dp[i][j] is computed in constant time (using previously computed subproblems).
  • Time complexity: O(n^2)
  • Space complexity: O(n^2) for the dp table.

Summary

The Longest Palindromic Subsequence problem is a classic example of dynamic programming, where overlapping subproblems and optimal substructure allow us to avoid brute-force enumeration. By breaking the problem into manageable subproblems and storing their solutions, we achieve an efficient O(n^2) solution. The approach is elegant because it leverages the recursive structure of palindromes and systematically builds up the answer using a simple table.