LC 1216 [H] Valid Palindrome III - ALawliet/algorithms GitHub Wiki

LPS (longest palindromic subsequence) edit distance where only deletion is allowed between s and reversed(s)

f(i,j) is the edit distance of s1[:i] and s2[:j] (i.e. the number of operations to make s1[:i] and s2[:j] the same)
f(i,j) = f(i-1,j-1) if s1[i-1]==s2[j-1]
f(i,j) = 1+min(f(i-1,j), f(i,j-1)), if s1[i-1]!=s2[j-1]
f(0,j) = j and f(i,0) = i

class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        T = [[0] * (n + 1) for _ in range(n + 1)] 

        for r in range(n + 1): 
            for c in range(n + 1):
                
                # if one of them is empty we have to delete the entire other
                if not r or not c: # if r == 0 then c, if c == 0 then r
                    T[r][c] = r or c 
                    
                # if last character is the same then no need to delete any of these last 2
                elif s[r-1] == s[n-c]: # reversed s[c-1]
                    T[r][c] = T[r-1][c-1] 
                    
                # if last characters are not the same then delete either or to get min
                else: 
                    T[r][c] = min(T[r-1][c], T[r][c-1]) + 1
        # print(T)
        # the distance == total number of deletions in one string + total number of deletions in the other
        # implies it has to be <= 2 * k
        # (removing at most k in each)
        return T[n][n] <= k * 2

def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        f = [[0]*(n+1) for _ in range(n+1)]
        f[0] = list(range(n+1))
        rs = "".join(reversed(s))
        for i in range(1, n+1):
            f[i][0] = i
            for j in range(1, n+1):
                if s[i-1] == rs[j-1]:
                    f[i][j] = f[i-1][j-1]
                else:
                    f[i][j] = 1 + min(f[i-1][j], f[i][j-1]) # delete s[i-1] or rs[j-1]
        return f[n][n] <= 2*k