Longest Palindromic Subsequence

How it works

The bottom-up DP approach can be optimized for space. When filling the DP table, each cell only depends on cells from the current and previous rows (or in this formulation, the current row and the previous diagonal value). By processing in the right order and keeping track of just the necessary values, we can reduce space from O(n^2) to O(n).

Steps

1. Create a 1D DP array of size n.
2. Iterate i from n-1 down to 0:
   • Set dp[i] = 1 (single character palindrome).
   • Track prev to store the previous diagonal value.
   • For each j from i+1 to n-1:
     • Save current dp[j] before updating.
     • If s[i] == s[j], set dp[j] = prev + 2.
     • Otherwise, set dp[j] = max(dp[j], dp[j-1]).
     • Update prev with the saved value.
3. Return dp[n-1].

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(n)

Things to watch for

Confusing Subsequence with Substring

A subsequence does not require contiguous characters, while a substring does. For the string "bbbab", the longest palindromic subsequence is "bbbb" (length 4), but the longest palindromic substring is "bbb" (length 3). Make sure your solution allows skipping characters when they do not contribute to the palindrome.

Incorrect Base Case Handling

When implementing the recursive or DP solution, a common error is mishandling the base cases. A single character (i == j) is always a palindrome of length 1, and when i > j (empty range), the length is 0. Forgetting to return 1 for single characters or incorrectly initializing the DP table leads to off-by-one errors.

Wrong Iteration Order in Bottom-Up DP

In the bottom-up approach, the DP table must be filled in the correct order so that smaller subproblems are solved before larger ones. You need to iterate i from n-1 down to 0 and j from i to n-1. Iterating in the wrong direction causes the algorithm to read uncomputed values, producing incorrect results.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [0] * n

        for i in range(n - 1, -1, -1):
            dp[i] = 1
            prev = 0
            for j in range(i + 1, n):
                temp = dp[j]

                if s[i] == s[j]:
                    dp[j] = prev + 2
                else:
                    dp[j] = max(dp[j], dp[j - 1])

                prev = temp

        return dp[n - 1]

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<int> dp(n, 0);

        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1;
            int prev = 0;
            for (int j = i + 1; j < n; j++) {
                int temp = dp[j];

                if (s[i] == s[j]) {
                    dp[j] = prev + 2;
                } else {
                    dp[j] = max(dp[j], dp[j - 1]);
                }

                prev = temp;
            }
        }

        return dp[n - 1];
    }
};