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 subsequence ; function to calculate minimum number of deletions ; Find longest palindromic subsequence ; After removing characters other than the lps , we get palindrome . ; Driver Code
function lps ( str ) { let n = str . length ; let L = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { L [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { L [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i < n ; i ++ ) L [ i ] [ i ] = 1 ; for ( let cl = 2 ; cl <= n ; cl ++ ) { for ( let i = 0 ; i < n - cl + 1 ; i ++ ) { let 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 ] = Math . max ( L [ i ] [ j - 1 ] , L [ i + 1 ] [ j ] ) ; } } return L [ 0 ] [ n - 1 ] ; } function minimumNumberOfDeletions ( str ) { let n = str . length ; let len = lps ( str ) ; return ( n - len ) ; } let str = " " ; document . write ( " " + " " + minimumNumberOfDeletions ( str ) ) ;