Minimum number of deletions to make a string palindrome

Given a string of size ‘n’. The task is to remove or delete the minimum number of characters from the string so that the resultant string is a palindrome.

Note: The order of characters should be maintained.

Examples :

Input : aebcbda Output : 2 Remove characters ‘e’ and ‘d’ Resultant string will be ‘abcba’ which is a palindromic string

Input : geeksforgeeks Output : 8

def transformation(s1,s2,i,j, dp):
     
    if i>=len(s1) or j>=len(s2):
        return 0
     
    if s1[i]==s2[j]:
         
        dp[i][j]=1+transformation(s1,s2,i+1,j+1,dp)
         
    if dp[i][j]!=-1:
         
        return dp[i][j]
     
    else:
        dp[i][j]=max(transformation(s1,s2,i,j+i,dp),
                     transformation(s1,s2,i+1,j,dp))
         
    return dp[-1][-1]

s1 = "geeksforgeeks"
s2 = "geeks"
dp=[[-1 for _ in range(len(s1)+1)] for _ in range(len(s2)+1)]
transformation(s1,s2,0,0,dp)

5