⚡Flashcard Drill➔
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

  1. dp[i][j] is the length of the longest palindromic subsequence of s[i..j].
  2. If s[i] == s[j], they wrap the inner palindrome, so dp[i][j] = dp[i+1][j-1] + 2.
  3. Otherwise one of the ends is excluded, so dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems