Leetcode 1216 Valid Palindrome III

Problem statement

https://leetcode.com/problems/design-file-system/

Solution

The idea is to use dp with state dp(i, j) be minimum number symbols deleted to get s[i:j+1] palindrome.

1. If we have s[i] == s[j], we need to consider problem dp(i + 1, j - 1).
2. In the opposite case either starting or ending symbol must be deleted, because it will break palindrome property.

Complexity

Time and space complexity is O(n^2).

Code

class Solution:
    def isValidPalindrome(self, s, k):
        n = len(s)

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