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

Hiring now

Adobe has 203 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

2027 Intern - Solutions Consulting
Paris
2027 Intern - Communications
San Francisco
Adobe Intern FY27
Bangalore

Or practice this question first

Next question