Longest Palindromic Subsequence
Problem
Given a string s, return the length of the longest palindromic subsequence in s.
- 1 ≤ s.length ≤ 1000
- s consists only of lowercase English letters.
Example
s = "bbbab"4The longest palindromic subsequence is "bbbb". The recursive approach explores all subsequences by comparing characters at the current left and right indices. When characters match, it adds 2 to the result of the inner substring. When they don't match, it explores both possibilities of excluding one character from either end and takes the maximum. Memoization caches results for subproblems to avoid redundant computations. For example, starting with indices (0,4), the algorithm compares 'b' and 'b' (match), then recursively solves for (1,3), and so on, building up the solution from smaller substrings.
Approach
Straightforward Solution
A brute-force approach tries all subsequences, which is exponential in time because it explores every combination of characters.
Core Observation
The longest palindromic subsequence problem exhibits optimal substructure: the solution for a substring depends on solutions to its smaller substrings. Specifically, if the characters at the ends match, the problem reduces to the inner substring plus 2; otherwise, it reduces to the maximum of excluding one end.
Path to Optimal
PreviewRecognizing the overlapping subproblems and optimal substructure leads to a recursive solution with memoization (top-down DP). The recursion explores substrings defined by left and right indices, caching results to avoid recomputation…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a recursive DFS with memoization keyed by substring indices (l, r). If characters at l and r match, add 2 plus the result of the inner substring…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n^2)
There are O(n^2) possible substrings defined by pairs of indices (l, r). Each substring is computed once and stored in memo, so the total time is quadratic.
Space
O(n^2)
The memo dictionary stores results for each substring (l, r), requiring O(n^2) auxiliary space. The recursion stack depth is O(n), which is dominated by the memo size.
Pattern Spotlight
Dynamic Programming (Top-Down Memoized Recursion)
When a problem involves finding an optimal subsequence or substring with overlapping subproblems, model it as a recursive function on substring indices and cache results to avoid exponential recomputation.
Solution
| 1 | class Solution: |
| 2 | def longestPalindromeSubseq(self, s: str) -> int: |
| 3 | n = len(s) |
| 4 | memo = {} |
| 5 | |
| 6 | def dfs(l, r): |
| 7 | |
| 8 | if l > r: |
| 9 | return 0 |
| 10 | |
| 11 | if l == r: |
| 12 | return 1 |
| 13 | |
| 14 | if (l, r) in memo: |
| 15 | return memo[(l, r)] |
| 16 | |
| 17 | if s[l] == s[r]: |
| 18 | ans = 2 + dfs(l+1, r-1) |
| 19 | else: |
| 20 | ans = max(dfs(l+1, r), dfs(l, r-1)) |
| 21 | |
| 22 | memo[(l, r)] = ans |
| 23 | return ans |
| 24 | |
| 25 | return dfs(0, n-1) |
Step-by-Step Solution
Cache Subproblem Results to Avoid Redundant Computation
| 4 | memo = {} |
| 14 | if (l, r) in memo: |
| 15 | return memo[(l, r)] |
| 22 | memo[(l, r)] = ans |
Objective
To store the results of longest palindromic subsequence computations for substrings defined by indices (l, r).
Key Insight
Memoization transforms the naive exponential recursion into a polynomial-time algorithm by caching results for each substring. This prevents the same substring from being recomputed multiple times, which is the main source of inefficiency in the brute-force approach. The dictionary key (l, r) uniquely identifies each subproblem.
Interview Quick-Check
Core Logic
Memoization uses a dictionary keyed by substring indices to store and retrieve results, ensuring each subproblem is solved once.
Common Pitfalls & Bugs
Forgetting to memoize or incorrectly keying the cache leads to exponential time due to repeated subproblem evaluations.
Recursively Compute Longest Palindromic Subsequence with Base Cases
To define the recursive logic that computes the longest palindromic subsequence length for substring s[l:r+1].
Initiate Recursive Computation from Full String Range
To start the recursive process by computing the longest palindromic subsequence for the entire string.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
if (l, r) in memo:Check if the result for substring (l, r) is already cached in memo.
Memoization lookup is the key optimization that reduces the exponential recursion tree to polynomial time by ensuring each substring is solved once.
ans = 2 + dfs(l+1, r-1)Calculate answer as 2 plus the result of the inner substring (l+1, r-1) when characters match.
This recurrence captures the core DP relation: when ends match, the longest palindromic subsequence length is 2 plus the inner substring's length, which is the fundamental building block of the solution.
memo = {}Initialize a memoization dictionary to cache subproblem results.
This cache prevents redundant computations by storing results for each substring, transforming exponential recursion into polynomial time.
Full line-by-line criticality + rationale for all 16 lines available on Pro.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to polynomial in this recursive solution?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Longest Palindromic Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Longest Palindromic Subsequence drill