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
- Deleting the fewest characters to reach a palindrome is equivalent to keeping the longest palindromic subsequence.
- So the answer is
n - LPS(s) <= k, whereLPSis the longest palindromic subsequence length. - Compute
LPSwith an interval DP:dp[i][j]is the LPS length ofs[i..j]. - When
s[i] == s[j],dp[i][j] = dp[i+1][j-1] + 2; otherwisedp[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.