1216. Valid Palindrome III

Option 1: bottom up (can be further optimized with using 1d dp array)

step 1: convert the problem to "finding the longest palindromic subsequence (LPS)", which requires DP

step 2: for LPS

base case: length of 1 and 2

inference:

       ```
       if s[i] == s[j]:
         dp[i][j] = dp[i+1][j-1] + 2
       else:
         dp[i][j] = max(dp[i][j-1], dp[i+1][j])
      ```

to infer dp[i][j], we need to ensure dp[i+1][j-1], dp[i][j-1] and dp[i+1][j] are ready. This is guaranteed because we have built base case where the length is 2. We then derive the case where length is 3, and it relies on cases where length is 1 and 2. We know that we have filled all dp where length is 1 and 2.

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)

        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
            if i < n - 1:
                dp[i][i+1] = 2 if s[i] == s[i+1] else 1
        
        for length in range(3, n+1):
            for i in range(n):
                j = i + length - 1
                if j >= n:
                    break
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i+1][j])
        
        target = dp[0][n-1]

        return (n - target) <= k

Option 2: bottom down

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
    
        @lru_cache(None)
        def longest_palindromic_subseq(i, j):
            if i > j:
                return 0
            if i == j:
                return 1
            if s[i] == s[j]:
                return longest_palindromic_subseq(i+1, j-1) + 2
            return max(longest_palindromic_subseq(i+1, j), longest_palindromic_subseq(i, j-1))

        n = len(s)
        lps_len = longest_palindromic_subseq(0, n-1)
        return (n - lps_len) <= k

another solution easy to understand

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

1216. Valid Palindrome III - cocoder39/coco39_LC GitHub Wiki