Make a String Palindromic with at Most K Deletions

Question

The question asks the candidate to determine if a given string can be transformed into a palindrome by deleting at most K characters.

Codemia · Accepted Answer

To determine if a string can be made palindromic with at most K deletions, we can use a two-pointer technique combined with recursion or dynamic programming. The idea is to compare characters from both ends of the string and decide whether to delete a character from either end when they do not match.

1. Initialize two pointers, `left` at the beginning and `right` at the end of the string.
2. If the characters at these pointers match, move both pointers inward.
3. If they do not match, decrement K and either move `left` or `right` inward, depending on which character is deleted.
4. If K becomes negative, return false. If the pointers cross, return true.

Here is a Python implementation of this algorithm:

```python
def can_make_palindrome(s: str, k: int) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] == s[right]:
            left += 1
            right -= 1
        else:
            k -= 1
            if k < 0:
                return False
            # Try deleting either character
            return can_make_palindrome(s[left + 1:right + 1], k) or can_make_palindrome(s[left:right], k)
    return True
```

The time complexity of this approach is O(n * K), where n is the length of the string and K is the maximum number of deletions allowed. This is due to the recursive calls made when characters do not match. The space complexity is O(1) for the pointers, but the recursion stack could go up to O(K) in the worst case.

While this recursive approach is straightforward, it may not be the most efficient for larger strings or higher values of K. An alternative approach using dynamic programming could store results of subproblems to avoid redundant calculations, potentially improving performance.

Consider edge cases such as an empty string, a string that is already a palindrome, or cases where K is larger than the length of the string. Each of these cases should be handled appropriately to ensure the algorithm works under all conditions.

Make a String Palindromic with at Most K Deletions

Meta

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string