BinarySearch 0654 Create Palindrome After Deleting at Most K Characters

Problem statement

https://binarysearch.com/problems/Create-Palindrome-After-Deleting-at-Most-K-Characters/

Solution

Variation of Leetcode 1312. Minimum Insertion Steps to Make a String Palindrome, but here we delete, not add, but minimum number of steps will be the same. What we need to do in the end is check if it is <= k.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def solve(self, s, k):
        @lru_cache(None)
        def dp(i, j):
            if j <= i: return 0
            if s[i] == s[j]: return dp(i + 1, j - 1)
            return min(dp(i + 1, j), dp(i, j - 1)) + 1
        
        return dp(0, len(s) - 1) <= k