Determine Whether a String Can Become a Palindrome After K Deletions
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## 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
```text
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.
```
Overview: Determine whether at most k deletions can turn a string into a palindrome while preserving character order. Develop a dynamic-programming or equivalent formulation that explores mismatched ends without enumerating every subsequence.
Read the full Meta Software Engineer interview experience this question came from
Given a lowercase string s and a nonnegative integer k, return whether deleting at most k characters can make s a palindrome. Remaining characters must preserve their original order. Deleting fewer than k characters is allowed, and the empty string and every one-character string are palindromes.
Constraints
- 0 <= len(s) <= 2000.
- 0 <= k <= len(s).
- s contains only lowercase English letters.
- Deleting fewer than k characters is allowed.
- Remaining characters preserve their original order.
- The solution does not enumerate subsequences.
Examples
Input: ('abcdeca', 2)
Expected Output: True
Explanation: This is the first source example; deleting b and e leaves acdca.
Input: ('acdcb', 1)
Expected Output: False
Explanation: This is the second source example; one deletion cannot produce a palindrome.
Hints
- Define the minimum deletions required for each two-ended substring.
- When endpoints differ, one of them must be deleted; when they match, keep both.