NeetCode #717LC-516Medium2-D Dynamic Programming
← Back to All Problems#717 · #516 · Longest Palindromic Subsequence(最长回文子序列)
📌 Problem Statement & Constraints
Given a string
s, return the length of its longest palindromic subsequence. Constraints: 1 <= s.length <= 1000, and s consists of lowercase English letters.💡 Core Algorithmic Approaches
dp[i][j]is the length of the longest palindromic subsequence ofs[i..j].- If
s[i] == s[j], they wrap the inner palindrome, sodp[i][j] = dp[i+1][j-1] + 2. - Otherwise one of the ends is excluded, so
dp[i][j] = max(dp[i+1][j], dp[i][j-1]). - Every single character is a palindrome of length 1, giving the diagonal base case.
💻 Benchmark Python3 Implementation
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = 2 + (dp[i + 1][j - 1] if length > 2 else 0)
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): each interval is solved once.
💾 Space Complexity
O(n^2), reducible to O(n).
⚠️ Interview Pitfalls & Follow-ups
- Using
dp[i+1][j-1]for length 2: that index is out of range, so the explicit base of 2 is needed. - Confusing subsequence with substring: a substring must be contiguous and needs a different DP.
- Omitting
dp[i][i] = 1: single characters are the base palindromes. - Iterating by start index: intervals must be processed by increasing length so the inner intervals are ready.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.