How to Solve Longest Palindromic Subsequence on LeetCode
The Longest Palindromic Subsequence problem is a classic DP string question, perfect for showing your mastery of subproblem analysis.
Problem Statement
Given a string s, return the length of the longest palindromic subsequence in s.
A subsequence is a sequence that can be derived by deleting zero or more characters without changing the order.
Example:
Input: s = "bbbab"
Output: 4
Explanation: One LPS is "bbbb".
Why This Problem Matters for Interviews
This problem:
- Demonstrates dynamic programming table design
- Tests your subproblem analysis and indexing
- Helps you discuss overlapping subproblems in strings
Dynamic Programming Approach to Longest Palindromic Subsequence
2D DP Table (Optimal)
Let dp[i][j] be the length of the LPS in s[i:j+1].
Time Complexity: O(n^2)
Space Complexity: O(n^2)
def longestPalindromeSubseq(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]
Key Interview Talking Points
- Subsequence vs substring distinction
- Table construction and diagonal filling
- Space optimization to 1D array (if asked)
- Reconstructing the LPS (for follow-up)
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DP Table | O(n^2) | O(n^2) |
Pro Interview Tips
- Draw the DP table with small examples.
- Explain cell dependencies in the table.
- Practice with test cases