Problem Description

Given a string s and an integer k, determine if s can be transformed into a palindrome by removing at most k characters. In other words, you may delete up to k characters from s, and after these deletions, the remaining string should read the same forwards and backwards.

Constraints:

• Only deletions are allowed; you cannot reorder or insert characters.
• You may not reuse deleted characters.
• There may be more than one way to achieve a valid palindrome, but you only need to determine if at least one way exists.
• 1 ≤ s.length ≤ 1000
• 0 ≤ k ≤ s.length
• s consists only of lowercase English letters.

Thought Process

At first glance, the problem resembles the classic palindrome check, but with the added flexibility of deleting up to k characters. A brute-force approach would be to try all possible ways of deleting up to k characters and check if any result in a palindrome. However, this is computationally expensive and impractical for strings of length up to 1000.

To optimize, we can draw on principles from dynamic programming (DP). The key insight is: the minimum number of deletions needed to make s a palindrome is related to the length of its longest palindromic subsequence (LPS). If the minimum deletions required is less than or equal to k, then it is possible.

Alternatively, we can use a DP approach to directly compute whether a substring can be made a palindrome using at most k deletions, by recursively checking and memoizing the results.

Solution Approach

• Recursive DP with Memoization:
  • Define a function dp(i, j) that returns the minimum number of deletions needed to make s[i..j] a palindrome.
  • Base Cases:
    • If i >= j, the substring is already a palindrome (empty or single character), so return 0.
  • Recursive Cases:
    • If s[i] == s[j], no deletion is needed at the ends, so recurse on dp(i+1, j-1).
    • If s[i] != s[j], we need to delete either s[i] or s[j]. So, compute 1 + min(dp(i+1, j), dp(i, j-1)).
  • Use memoization (caching) to avoid recomputing the same subproblems.
  • Finally, compare the result dp(0, n-1) to k. If it is less than or equal to k, return true; otherwise, false.
• Why this works: This approach efficiently finds the minimum deletions needed, and with memoization, runs in O(n^2) time.
• Alternative Approach via Longest Palindromic Subsequence:
  • The minimum deletions needed = s.length - LPS(s).
  • If this value is ≤ k, return true.
  • Both approaches have similar DP structure and complexity.

Example Walkthrough

Example: s = "abcdeca", k = 2

• We want to know if we can remove at most 2 characters to make it a palindrome.
• Let's check possible palindromic forms:
  • Remove 'b' and 'e' → "acdca", which is a palindrome.
  • Alternatively, remove 'c' and 'e' → "abdca", which is not a palindrome.
• Our DP will find that the minimum deletions needed is 2, which is ≤ k.
• So, the answer is true.
• DP Table Evolution:
  • For each substring, we check characters at the ends. If they match, move inwards. If not, try deleting from either end and take the minimum.
  • By filling the table bottom up or using memoization, we avoid redundant computations.

Time and Space Complexity

• Brute-force Approach:
  • Tries all combinations of up to k deletions. For each character, decide to delete or not.
  • Time Complexity: O(2^n), which is infeasible for large n.
• Optimized DP Approach:
  • There are O(n^2) possible substrings. Each dp(i, j) is computed once.
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2) for the memoization table.

Summary

The "Valid Palindrome III" problem asks whether a string can be made into a palindrome by deleting at most k characters. Brute-force is impractical, but dynamic programming—either via direct minimum deletions or longest palindromic subsequence—offers an elegant O(n^2) solution. The core insight is to break the problem into subproblems of substrings, use memoization to avoid redundant work, and check if the minimum deletions needed fit within the allowed budget k.

Code Implementation

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        from functools import lru_cache

        n = len(s)

        @lru_cache(maxsize=None)
        def dp(i, j):
            if i >= j:
                return 0
            if s[i] == s[j]:
                return dp(i + 1, j - 1)
            else:
                return 1 + min(dp(i + 1, j), dp(i, j - 1))

        return dp(0, n - 1) <= k
      

class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        vector<vector<int>> memo(n, vector<int>(n, -1));

        function<int(int, int)> dp = [&](int i, int j) {
            if (i >= j) return 0;
            if (memo[i][j] != -1) return memo[i][j];
            if (s[i] == s[j])
                memo[i][j] = dp(i + 1, j - 1);
            else
                memo[i][j] = 1 + min(dp(i + 1, j), dp(i, j - 1));
            return memo[i][j];
        };

        return dp(0, n - 1) <= k;
    }
};
      

class Solution {
    public boolean isValidPalindrome(String s, int k) {
        int n = s.length();
        Integer[][] memo = new Integer[n][n];

        return dp(s, 0, n - 1, memo) <= k;
    }

    private int dp(String s, int i, int j, Integer[][] memo) {
        if (i >= j) return 0;
        if (memo[i][j] != null) return memo[i][j];
        if (s.charAt(i) == s.charAt(j))
            memo[i][j] = dp(s, i + 1, j - 1, memo);
        else
            memo[i][j] = 1 + Math.min(dp(s, i + 1, j, memo), dp(s, i, j - 1, memo));
        return memo[i][j];
    }
}
      

var isValidPalindrome = function(s, k) {
    const n = s.length;
    const memo = Array.from({length: n}, () => Array(n).fill(-1));

    function dp(i, j) {
        if (i >= j) return 0;
        if (memo[i][j] !== -1) return memo[i][j];
        if (s[i] === s[j])
            memo[i][j] = dp(i + 1, j - 1);
        else
            memo[i][j] = 1 + Math.min(dp(i + 1, j), dp(i, j - 1));
        return memo[i][j];
    }

    return dp(0, n - 1) <= k;
};