Minimum number of deletions to make a string palindrome | Returns the length of the longest palindromic subsequence in 'str ; Create a table to store results of subproblems ; Strings of length 1 are palindrome of length 1 ; Build the table . Note that the lower diagonal values of table are useless and not filled in the process . c1 is length of substring ; length of longest palindromic subseq ; function to calculate minimum number of deletions ; Find longest palindromic subsequence ; After removing characters other than the lps , we get palindrome . ; Driver Code
' NEW_LINE def lps ( str ) : NEW_LINE INDENT n = len ( str ) NEW_LINE L = [ [ 0 for x in range ( n ) ] for y in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT L [ i ] [ i ] = 1 NEW_LINE DEDENT for cl in range ( 2 , n + 1 ) : NEW_LINE INDENT for i in range ( n - cl + 1 ) : NEW_LINE INDENT j = i + cl - 1 NEW_LINE if ( str [ i ] == str [ j ] and cl == 2 ) : NEW_LINE INDENT L [ i ] [ j ] = 2 NEW_LINE DEDENT elif ( str [ i ] == str [ j ] ) : NEW_LINE INDENT L [ i ] [ j ] = L [ i + 1 ] [ j - 1 ] + 2 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i ] [ j - 1 ] , L [ i + 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT return L [ 0 ] [ n - 1 ] NEW_LINE DEDENT def minimumNumberOfDeletions ( str ) : NEW_LINE INDENT n = len ( str ) NEW_LINE l = lps ( str ) NEW_LINE return ( n - l ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str = " geeksforgeeks " NEW_LINE print ( " Minimum ▁ number ▁ of ▁ deletions ▁ = ▁ " , minimumNumberOfDeletions ( str ) ) NEW_LINE DEDENT