Determine Whether a String Can Become a Palindrome After K Deletions

Problem

Given a string s and a nonnegative integer k, return whether deleting at most k characters can make s a palindrome. Characters that remain must preserve their original order. The empty string and every one-character string are palindromes.

Constraints & Assumptions

• 0 <= len(s) <= 2,000.
• 0 <= k <= len(s).
• The input contains lowercase English letters.
• The solution should avoid enumerating all subsequences.

Clarifications

• Deleting fewer than k characters is allowed.
• A character may be deleted from either side of a mismatched pair.
• Return only a boolean, not the resulting palindrome.

Examples

s = "abcdeca", k = 2
output = true

s = "acdcb", k = 1
output = false

Hints

Hint: Measure what must be removed

Relate the minimum deletions to a longest palindromic subsequence or define a two-ended state.

Hint: Bound the work

A two-dimensional dynamic program is sufficient for the stated maximum length.

Determine Whether a String Can Become a Palindrome After K Deletions

Hints

1. Define the minimum deletions required for each two-ended substring.
2. When endpoints differ, one of them must be deleted; when they match, keep both.

Approach

For each substring, define the minimum deletions needed to make it a palindrome. Matching end characters can both remain, so the answer equals the inner substring's answer. Mismatched ends require deleting either the left or the right character, so the answer is one plus the smaller adjacent-substring answer. Evaluate these states from shorter substrings to longer ones. A one-dimensional array stores the previous-left row, while a saved diagonal value represents the inner substring, reducing space from quadratic to linear. The whole string is feasible exactly when its minimum deletion count is at most k.

• Time complexity: O(n^2)
• Space complexity: O(n)