680. Valid Palindrome II

time: O(N) either isPalindrome is not invoked or isPalindrome is invoked 2 times.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s)-1
        while left < right:
            if s[left] != s[right]:
                return self.isPalindrome(s, left+1, right) or self.isPalindrome(s, left, right-1)
            left += 1
            right -= 1        
        return True
            
    def isPalindrome(self, s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
                
        return True

follow up: you can delete up to k chars

from functools import lru_cache

class Solution:
    def validPalindrome(self, s: str) -> bool:
        return self.is_palindrome(s, 0, len(s)-1, 1)
    
    @lru_cache(None)
    def is_palindrome(self, s, left, right, k):
        if left >= right:
            return True
        if s[left] == s[right]:
            return self.is_palindrome(s, left+1, right-1, k)
        if k > 0:
            return self.is_palindrome(s, left+1, right, k-1) or self.is_palindrome(s, left, right-1, k-1)
        return False

there are O(k * n^2) unique states, so T = O(k * n * n)
space: O(k * n^2) unique states. O(n) for recursion stack: each step i or j moves at least one index, so at most O(n). total space is O(k * n * n)

680. Valid Palindrome II - cocoder39/coco39_LC GitHub Wiki