Katkat
Back

Check Whether Deleting at Most K Characters Can Form a Palindrome

MetaSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

Determine whether a string can be transformed into a palindrome by removing at most k characters. Tests dynamic programming, palindrome properties, and recursive search with branch bounding.

Problem Statement

Given a string s and an integer k, determine whether it is possible to transform s into a palindrome by removing at most k characters from it.

A palindrome is a string that reads the same backward as forward (e.g., "racecar", "aba", "").

Function Signature

def is_valid_palindrome(s: str, k: int) -> bool:
    pass

Constraints

  • 1 <= len(s) <= 2000
  • 0 <= k <= len(s)
  • s consists only of lowercase English letters.

Examples

Example 1:

Input: s = "abca", k = 1
Output: True
Explanation: Removing 'b' leaves "aca", which is a palindrome. Alternatively, removing 'c' leaves "aba".

Example 2:

Input: s = "abcdeca", k = 2
Output: True
Explanation: Removing 'b' and 'd' yields "aceca", which is a palindrome.

Example 3:

Input: s = "abcdef", k = 2
Output: False
Explanation: Any two removals leave at least four distinct characters that cannot form a palindrome.

Edge Cases

  • k == 0: s must already be a palindrome.
  • k >= len(s) - 1: Any string can be reduced to a single character (or empty string), which is always a palindrome, so return True.
  • s is already a palindrome with k > 0: Return True immediately.

Hints

Hint 1

Notice that removing at most k characters to form a palindrome is equivalent to checking if the Longest Palindromic Subsequence (LPS) of s has length at least len(s) - k.

Hint 2

The length of the Longest Palindromic Subsequence of a string s can be computed via DP in O(n^2) time, which corresponds to the Longest Common Subsequence (LCS) between s and reversed(s).

Hint 3

If k is much smaller than n, a recursive two-pointer approach with pruning that only explores up to k mismatches achieves O(n + 2^k) time and avoids allocating an O(n^2) table.

Follow-up questions

  • How would you optimize your solution if k is very small (e.g., k <= 5) compared to n = 100,000?
  • Can you reconstruct and return the actual resulting palindrome rather than just returning a boolean?
  • How can you optimize the space complexity of the O(n^2) DP approach to O(n)?