Minimum steps to delete a string by deleting substring comprising of same characters | Java 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
class GFG { static int N = 10 ; static int findMinimumDeletion ( int l , int r , int dp [ ] [ ] , String s ) { if ( l > r ) { return 0 ; } if ( l == r ) { return 1 ; } if ( dp [ l ] [ r ] != - 1 ) { return dp [ l ] [ r ] ; } int res = 1 + findMinimumDeletion ( l + 1 , r , dp , s ) ; for ( int i = l + 1 ; i <= r ; ++ i ) { if ( s . charAt ( l ) == s . charAt ( i ) ) { res = Math . min ( res , findMinimumDeletion ( l + 1 , i - 1 , dp , s ) + findMinimumDeletion ( i , r , dp , s ) ) ; } } return dp [ l ] [ r ] = res ; } public static void main ( String [ ] args ) { String s = " abcddcba " ; int n = s . length ( ) ; int dp [ ] [ ] = new int [ N ] [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } System . out . println ( findMinimumDeletion ( 0 , n - 1 , dp , s ) ) ; } }