Hard

Valid Palindrome III

LAB

Return true if s can become a palindrome after deleting at most k characters.

EXAMPLES

Example 1

Input
{
  "s": "abcdeca",
  "k": 2
}

Output
true

FUNCTION SHAPE

s: stringk: int→bool

SOLUTION NOTE

Think in reverse: if we can remove k chars, remaining chars form a palindromic subsequence. Check if LPS length >= n-k.

Reveal reference solution +

pythonREFERENCE

def isValidPalindrome(self, s: str, k: int) -> bool:
    @cache
    def dp(i, j):
        if i >= j: return i == j
        if s[i] == s[j]:
            return 2 + dp(i + 1, j - 1)
        return max(dp(i + 1, j), dp(i, j - 1))

    return dp(0, len(s) - 1) >= len(s) - k

TimeO(n²)

SpaceO(n²)

Open on LeetCode ↗