Minimum steps to delete a string by deleting substring comprising of same characters | PHP 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
< ? php $ GLOBALS [ ' 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 ] ; $ res = 1 + findMinimumDeletion ( $ l + 1 , $ r , $ dp , $ s ) ; for ( $ i = $ l + 1 ; $ i <= $ r ; ++ $ i ) { if ( $ s [ $ l ] == $ s [ $ i ] ) $ res = min ( $ res , findMinimumDeletion ( $ l + 1 , $ i - 1 , $ dp , $ s ) + findMinimumDeletion ( $ i , $ r , $ dp , $ s ) ) ; } return $ dp [ $ l ] [ $ r ] = $ res ; } $ s = " abcddcba " ; $ n = strlen ( $ s ) ; $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ GLOBALS [ ' N ' ] ; $ i ++ ) for ( $ j = 0 ; $ j < $ GLOBALS [ ' N ' ] ; $ j ++ ) $ dp [ $ i ] [ $ j ] = -1 ; echo findMinimumDeletion ( 0 , $ n - 1 , $ dp , $ s ) ; ? >