Longest Palindromic Subsequence - Solution & Explanation

Problem Overview: Given a string s, return the length of the longest subsequence that reads the same forward and backward. Unlike substrings, subsequences do not need to be contiguous, so you can skip characters while preserving order.

This problem appears frequently in string and dynamic programming interviews. The key observation: if the first and last characters of a substring match, they can contribute to a palindrome. Otherwise, you must skip one side and try smaller subproblems.

Approach 1: Recursive Approach with Memoization (Top-Down DP) (Time: O(n²), Space: O(n²))

Define a recursive function dfs(i, j) that returns the longest palindromic subsequence within the substring s[i..j]. If s[i] == s[j], those characters form the ends of a palindrome, so the answer becomes 2 + dfs(i+1, j-1). If they differ, skip one side and compute max(dfs(i+1, j), dfs(i, j-1)). Without optimization this recursion explodes exponentially, because the same ranges repeat many times.

Memoization fixes this by caching results for each pair (i, j). Since there are only n * n possible substrings, the recursion runs in O(n²) time and stores results in an O(n²) memo table. This approach is intuitive because it mirrors the mathematical recurrence directly.

Approach 2: Dynamic Programming (Bottom-Up Table) (Time: O(n²), Space: O(n²))

The bottom-up version fills a DP table where dp[i][j] represents the length of the longest palindromic subsequence in s[i..j]. Start with base cases where every single character is a palindrome of length 1. Then expand the window size from smaller substrings to larger ones.

For each pair of indices:

If s[i] == s[j], extend the inner palindrome: dp[i][j] = 2 + dp[i+1][j-1]. If they differ, carry forward the best subsequence by skipping one side: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

The table is typically filled from the bottom of the string toward the start so that subproblems like dp[i+1][j-1] are already computed. This produces the final answer at dp[0][n-1]. Because every substring pair is processed exactly once, the runtime is O(n²) and the memory cost is also O(n²).

Another useful insight: the problem is equivalent to computing the Longest Common Subsequence between the string and its reverse. That perspective often helps when connecting multiple dynamic programming patterns together.

Recommended for interviews: The bottom-up dynamic programming approach is what most interviewers expect. It shows you understand overlapping subproblems, table construction, and state transitions. Starting with the recursive relation demonstrates intuition, then converting it to memoization or a DP table shows strong problem‑solving discipline.