Minimum number of deletions to make a string palindrome | Set 2 | Javascript program to find minimum deletions to make palindrome . ; Find reverse of input string ; Create a DP table for storing edit distance of string and reverse . ; Find edit distance between input and revInput considering only delete operation . ; Go from bottom left to top right and find the minimum ; Driver Code
function getLevenstein ( input ) { let revInput = ( input ) . split ( " " ) ; revInput = revInput . reverse ( ) ; let n = input . length ; let dp = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { dp [ i ] = new Array ( n + 1 ) ; for ( let j = 0 ; j < n + 1 ; j ++ ) dp [ i ] [ j ] = 0 ; } for ( let i = 0 ; i <= n ; ++ i ) { dp [ 0 ] [ i ] = i ; dp [ i ] [ 0 ] = i ; } for ( let i = 1 ; i <= n ; ++ i ) { for ( let j = 1 ; j <= n ; ++ j ) { if ( input [ i - 1 ] == revInput [ j - 1 ] ) dp [ i ] [ j ] = dp [ i - 1 ] [ j - 1 ] ; else dp [ i ] [ j ] = 1 + Math . min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; } } let res = Number . MAX_VALUE ; for ( let i = n , j = 0 ; i >= 0 ; i -- , j ++ ) { res = Math . min ( res , dp [ i ] [ j ] ) ; if ( i < n ) res = Math . min ( res , dp [ i + 1 ] [ j ] ) ; if ( i > 0 ) res = Math . min ( res , dp [ i - 1 ] [ j ] ) ; } return res ; } let input = ( " " ) ; document . write ( getLevenstein ( input ) ) ;