Coding

Valid Palindrome III

Asked at

AdobeBBarclays

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string s and an integer k, return true if s is a k-palindrome.

A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Input: s = "abcdeca", k = 2 Output: true Explanation: Remove 'b' and 'e' characters.

Input: s = "abbababa", k = 1 Output: true

Input s = "bacabaaa", k =2

1 <= s.length <= 1000 s consists of only lowercase English letters. 1 <= k <= s.length

cpp

class Solution {
public:
    bool isValidPalindrome(string s, int k) {
       //User code goes here
    }
};

java

class Solution {
    public boolean isValidPalindrome(String s, int k) {
        // User code goes here
    }
}

python

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        # User code goes here
        return False

javascript

class Solution {
    isValidPalindrome(s, k) {
        // User code goes here
    }
}

csharp

public class Solution
{
    public bool IsValidPalindrome(string s, int k)
    {
        // User code goes here
        return false;
    }
}

func isValidPalindrome(s string, k int) bool {
	// User code goes here
	return false
}

Stuck? Show a way to structure it+

01Compute the minimum deletions needed to make the string a palindrome, or equivalently its longest palindromic subsequence.
02Use matching ends directly; otherwise discard one end and take the better state.
03Return whether the minimum deletion count is at most k.
04Memoize or fill bottom-up so overlapping intervals are solved once.

Reference answer

One approach computes the longest palindromic subsequence LPS; the minimum deletions needed are n - LPS, so return whether that value is at most k. LPS(s) is the longest common subsequence between s and reverse(s), computable in O(n squared) time and O(n) optimized space. An interval DP is equally direct: delete(i,j) = 0 when i >= j; if s[i] == s[j], use delete(i+1,j-1), otherwise use 1 + min(delete(i+1,j), delete(i,j-1)). The string is a k-palindrome when delete(0,n-1) <= k. Memoization or bottom-up filling avoids exponential recursion. Since only a boolean threshold is needed, states greater than k may be capped or pruned, but the standard quadratic solution is usually the clearest.

Then expect these follow-ups

Why is minimum deletion count n minus LPS?
Tests: equivalence proof
How would you construct the resulting palindrome?
Tests: reconstruction

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question