Minimum steps to delete a string by deleting substring comprising of same characters | JavaScript implementation of the approach ; Function to return the minimum number of delete operations ; When a single character is deleted ; When a group of consecutive characters are deleted if any of them matches ; When both the characters are same then delete the letters in between them ; Memoize ; Driver code
var N = 10 ; function findMinimumDeletion ( l , r , dp , s ) { if ( l > r ) return 0 ; if ( l == r ) return 1 ; if ( dp [ l ] [ r ] != - 1 ) return dp [ l ] [ r ] ; var res = 1 + findMinimumDeletion ( l + 1 , r , dp , s ) ; for ( var i = l + 1 ; i <= r ; ++ i ) { if ( s [ l ] == s [ i ] ) res = Math . min ( res , findMinimumDeletion ( l + 1 , i - 1 , dp , s ) + findMinimumDeletion ( i , r , dp , s ) ) ; } return dp [ l ] [ r ] = res ; } var s = " " ; var n = s . length ; var dp = Array . from ( Array ( N ) , ( ) => Array ( N ) . fill ( - 1 ) ) ; document . write ( findMinimumDeletion ( 0 , n - 1 , dp , s ) ) ;