⚡Flashcard Drill➔
NeetCode #709LC-1216Hard1-D Dynamic Programming
← Back to All Problems

#709 · #1216 · Valid Palindrome III(验证回文串 III)

📌 Problem Statement & Constraints

Given a string s and an integer k, return true if s can be turned into a palindrome by deleting at most k characters. Constraints: 1 <= s.length <= 1000, 0 <= k <= s.length, and s consists of lowercase English letters.

💡 Core Algorithmic Approaches

  1. Deleting the fewest characters to reach a palindrome is equivalent to keeping the longest palindromic subsequence.
  2. So the answer is n - LPS(s) <= k, where LPS is the longest palindromic subsequence length.
  3. Compute LPS with an interval DP: dp[i][j] is the LPS length of s[i..j].
  4. When s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

💻 Benchmark Python3 Implementation

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1               # every single character
        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 n - dp[0][n - 1] <= k

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): every interval is filled once.
💾 Space Complexity
O(n^2): the DP table, reducible to O(n).

⚠️ Interview Pitfalls & Follow-ups

  • Computing the edit distance to the reversed string: that counts insertions too, while only deletions are allowed, so the LPS route is correct.
  • Handling the length-2 case with dp[i+1][j-1]: that index is out of range, so the explicit base of 2 is needed.
  • Comparing n - LPS < k: the limit is inclusive, so the test is <= k.
  • Returning the LPS length: the function must return a boolean.
⚡
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 1-D Dynamic Programming Problems