Minimum steps to delete a string by deleting substring comprising of same characters | C # 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
using System ; 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 [ l ] == s [ 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 ; } } Console . WriteLine ( findMinimumDeletion ( 0 , n - 1 , dp , s ) ) ; } }