Make a String Palindromic with at Most K Deletions
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement `can_make_palindrome(text, k)`.
Return whether deleting at most `k` characters from `text` can leave a palindrome. Characters that remain must preserve their original relative order. `k` is nonnegative, and deleting no characters is allowed.
For example, `text = "abca"` and `k = 1` return `true`, while `text = "abc"` and `k = 1` return `false`.
```hint Matching ends cost nothing
If the current left and right characters match, move both boundaries inward without using a deletion.
```
```hint A mismatch creates two choices
Delete either the left character or the right character, reduce the remaining deletion budget, and memoize the state formed by both boundaries and that budget.
```
### Discussion Extensions
- How can computing the minimum deletions for every substring remove `k` from the memoization state?
- What is the worst-case time and space complexity of the memoized boundary-and-budget solution?
Quick Answer: Decide whether deleting at most k characters can turn a string into a palindrome while preserving order. Explore memoized two-pointer choices, matching-end shortcuts, and the connection to minimum-deletion dynamic programming.
Implement can_make_palindrome(text, k). Return whether deleting at most k characters, while preserving the relative order of all remaining characters, can leave a palindrome.
Constraints
- 0 <= text.length <= 200.
- The text contains ASCII characters and 0 <= k <= text.length.
- Deleting no characters is allowed, and remaining characters keep their original relative order.
Examples
Input: ('abca', 1)
Expected Output: True
Input: ('abc', 1)
Expected Output: False
Hints
- For each substring, matching endpoints add no deletion; a mismatch deletes either the left or right endpoint.
- Computing the minimum deletions per substring removes k from the dynamic-programming state, so the final minimum can be compared with k.