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
< ? php function lps ( $ str ) { $ n = strlen ( $ str ) ; $ L ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ L [ $ i ] [ $ i ] = 1 ; for ( $ cl = 2 ; $ cl <= $ n ; $ cl ++ ) { for ( $ i = 0 ; $ i < $ n - $ cl + 1 ; $ i ++ ) { $ j = $ i + $ cl - 1 ; if ( $ str [ $ i ] == $ str [ $ j ] && $ cl == 2 ) $ L [ $ i ] [ $ j ] = 2 ; else if ( $ str [ $ i ] == $ str [ $ j ] ) $ L [ $ i ] [ $ j ] = $ L [ $ i + 1 ] [ $ j - 1 ] + 2 ; else $ L [ $ i ] [ $ j ] = max ( $ L [ $ i ] [ $ j - 1 ] , $ L [ $ i + 1 ] [ $ j ] ) ; } } return $ L [ 0 ] [ $ n - 1 ] ; } function minimumNumberOfDeletions ( $ str ) { $ n = strlen ( $ str ) ; $ len = lps ( $ str ) ; return ( $ n - $ len ) ; } { $ str = " geeksforgeeks " ; echo " Minimum ▁ number ▁ of ▁ deletions ▁ = ▁ " , minimumNumberOfDeletions ( $ str ) ; return 0 ; } ? >