Quick 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.

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

  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.

Loading coding console...

Show the approach

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)