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
Recognizing 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. This reduces the complexity from exponential to polynomial.
Optimal Approach
Use 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. Otherwise, take the max of excluding either the left or right character. Memoization ensures each substring is solved once, yielding O(n^2) time and space complexity.
Time
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
| 6 | def dfs(l, r): |
| 8 | if l > r: |
| 9 | return 0 |
| 11 | if l == r: |
| 12 | return 1 |
| 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)) |
| 23 | return ans |
Objective
To define the recursive logic that computes the longest palindromic subsequence length for substring s[l:r+1].
Key Insight
The recursion handles two base cases: when the substring is empty (l > r), the length is 0; when the substring is a single character (l == r), the length is 1. For longer substrings, if the characters at the ends match, the solution is 2 plus the inner substring's solution. Otherwise, it is the maximum of excluding either the left or right character. This recursive decomposition exploits the problem's optimal substructure.
Interview Quick-Check
Core Logic
The recursion breaks the problem into smaller substrings, using base cases to terminate and combining results based on character matches.
State & Boundaries
Base cases ensure correct termination: empty substring returns 0, single character substring returns 1.
Common Pitfalls & Bugs
Incorrect base cases or missing them can cause infinite recursion or wrong results.
Initiate Recursive Computation from Full String Range
| 3 | n = len(s) |
| 25 | return dfs(0, n-1) |
Objective
To start the recursive process by computing the longest palindromic subsequence for the entire string.
Key Insight
Calling the recursive function with the full string indices (0, n-1) triggers the top-down DP process. This single call recursively breaks down the problem into smaller substrings, leveraging memoization to efficiently compute the final answer.
Interview Quick-Check
Core Logic
Starting from the full string range ensures the entire problem is solved by recursive decomposition.
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.
return memo[(l, r)]Return the cached result for substring (l, r) if available.
Returning cached results immediately prunes redundant recursive calls, preserving optimal time complexity.
if s[l] == s[r]:Check if characters at indices l and r match.
Matching characters at the ends of the substring indicate that these two characters can form part of a palindromic subsequence, allowing the solution to include both and recurse inward.
else:Otherwise, calculate answer as the maximum of excluding left or right character.
When ends don't match, the solution must exclude one character and take the best of the two resulting substrings, ensuring all subsequences are considered.
memo[(l, r)] = ansCache the computed answer for substring (l, r) in memo.
Storing the result ensures that future calls with the same substring reuse this computation, which is essential for the DP optimization.
if l > r:Check if the current substring is empty (l > r).
An empty substring has no characters, so the longest palindromic subsequence length is zero, serving as a base case to terminate recursion.
if l == r:Check if the current substring has a single character (l == r).
A single character is a palindrome of length one, serving as a base case for recursion.
ans = max(dfs(l+1, r), dfs(l, r-1))Compute max between dfs(l+1, r) and dfs(l, r-1) for non-matching ends.
This step explores both possibilities of excluding one end, ensuring the algorithm finds the longest palindromic subsequence by exhaustive but efficient search.
return dfs(0, n-1)Start the recursive computation for the entire string s from indices 0 to n-1.
This initial call triggers the top-down DP process that solves the problem by decomposing it into smaller substrings.
def dfs(l, r):Define the recursive function dfs to compute longest palindromic subsequence for substring s[l:r+1].
Encapsulating the recursive logic in a helper function allows clean management of substring indices and memoization.
return 0Return 0 for empty substring base case.
Returning zero here correctly terminates recursion for invalid substring ranges.
return 1Return 1 for single character substring base case.
Returning one here correctly identifies the smallest palindromic subsequence.
return ansReturn the computed answer for substring (l, r).
Returning the result completes the recursion step and propagates the solution up the call stack.
n = len(s)Calculate the length of the input string s.
Knowing the string length is essential for defining the initial substring boundaries and controlling recursion limits.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to polynomial in this recursive solution?
Because memoization caches the results of subproblems identified by substring indices, each unique subproblem is solved only once, preventing redundant recomputation of overlapping subproblems.
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