Minimum Deletions to make a string palindrome

'''
LCS variation: Here you have to do some deletions to get your output so deletion must be a subsequence, it can't be substring
because character might be removed from between so you must have a subsequence which is longest and it's also palindrome
so what you can do is find LCS of s and reversed(s) which will be longest subsequence of s which would be also palindrome
and that satisfies your requirement so total s lenght -lcs length is your answer.

'''
def fun(s1,s2,n,m,dp):
    if n<0 or m<0:
        return 0
    if dp[n][m]!=-1:
        return dp[n][m]
    if s1[n]==s2[m]:
        dp[n][m]=1+fun(s1,s2,n-1,m-1,dp)
    else:
        dp[n][m]=max(fun(s1,s2,n-1,m,dp),fun(s1,s2,n,m-1,dp))
    return dp[n][m]


class Solution:
    def minDeletions(self,s):
        dp=[[-1]*len(s) for _ in range(len(s))]
        s2=s[::-1]
        lcs=fun(s,s2,len(s)-1,len(s2)-1,dp)
        return len(s)-lcs