Valid Palindrome III - Solution & Explanation

Problem Overview: You are given a string s and an integer k. The task is to determine whether the string can become a palindrome after removing at most k characters. Deletions can occur at any index, but the relative order of remaining characters must stay the same.

The key observation: instead of thinking about which characters to delete, compute how close the string already is to being a palindrome. If the minimum number of deletions required is ≤ k, the answer is true.

Approach 1: Longest Palindromic Subsequence via LCS (O(n²) time, O(n²) space)

A string becomes a palindrome when its longest palindromic subsequence (LPS) is as large as possible. The minimum deletions required is n - LPS. You can compute LPS by finding the Longest Common Subsequence between the string and its reverse. Build a 2D DP table where dp[i][j] represents the LCS length between the first i characters of s and the first j characters of reverse(s). Each state compares characters and extends the subsequence if they match, otherwise it takes the maximum of adjacent states. If n - LPS ≤ k, the string is a valid k‑palindrome. This approach relies on classic dynamic programming over a string.

Approach 2: Direct DP for Minimum Deletions (O(n²) time, O(n²) space)

Instead of computing LPS indirectly, define a DP table dp[i][j] as the minimum deletions needed to make the substring s[i..j] a palindrome. If the characters match (s[i] == s[j]), no deletion is required and you inherit the result from dp[i+1][j-1]. If they differ, delete one side and take the better option: 1 + min(dp[i+1][j], dp[i][j-1]). Fill the table for increasing substring lengths. The final value dp[0][n-1] gives the minimum deletions needed for the entire string. Compare it with k. This formulation is often easier to reason about during interviews because it models the deletion operation directly.

Approach 3: Space-Optimized LCS DP (O(n²) time, O(n) space)

The LCS-based solution only depends on the previous row of the DP table. You can compress the 2D DP into two 1D arrays (or a single rolling array) while iterating through the reversed string. This reduces memory from O(n²) to O(n). The logic remains identical: compute LCS length, derive LPS, then check whether n - LPS ≤ k. Useful when the string length approaches the upper constraints and memory usage matters.

Recommended for interviews: The direct minimum-deletions DP is usually the clearest explanation. It demonstrates understanding of substring DP and state transitions. The LCS-based method is equally valid and often recognized quickly by experienced candidates because LPS = LCS(s, reverse(s)). Showing the brute reasoning about deletions first and then deriving the optimized DP demonstrates strong problem-solving depth.