Count of ways to empty given String by recursively removing all adjacent duplicates | C # implementation for the above approach ; Define the dp table globally ; Recursive function to calculate the dp values for range [ L , R ] ; The range is odd length ; The state is already calculated ; If the length is 2 ; Total answer for this state ; Variable to store the current answer . ; Remove characters s [ l ] and s [ i ] . ; Initialize all the states of dp to - 1 ; Calculate all Combinations ; Driver Code
using System ; using System . Collections . Generic ; class GFG { static int [ , ] dp = new int [ 505 , 505 ] ; static int [ , ] choose = new int [ 502 , 502 ] ; static int calc ( int l , int r , string s ) { if ( Math . Abs ( r - l ) % 2 == 0 ) { return 0 ; } if ( l > r ) { return dp [ l , r ] = 1 ; } if ( dp [ l , r ] != - 1 ) { return dp [ l , r ] ; } if ( ( r - l ) == 1 ) { if ( s [ l ] == s [ r ] ) { dp [ l , r ] = 1 ; } else { dp [ l , r ] = 0 ; } return dp [ l , r ] ; } int ans = 0 ; for ( int k = l + 1 ; k <= r ; k += 2 ) { int temp = 1 ; if ( s [ l ] == s [ k ] ) { temp = calc ( l + 1 , k - 1 , s ) * calc ( k + 1 , r , s ) * choose [ ( r - l + 1 ) / 2 , ( r - k ) / 2 ] ; ans += temp ; } } return dp [ l , r ] = ans ; } static int waysToClearString ( string S ) { for ( int i = 0 ; i < 505 ; i ++ ) { for ( int j = 0 ; j < 505 ; j ++ ) dp [ i , j ] = - 1 ; } int n = S . Length ; choose [ 0 , 0 ] = 1 ; for ( int i = 1 ; i <= n / 2 ; ++ i ) { choose [ i , 0 ] = 1 ; for ( int j = 1 ; j <= i ; ++ j ) { choose [ i , j ] = ( choose [ i - 1 , j ] + choose [ i - 1 , j - 1 ] ) ; } } return calc ( 0 , n - 1 , S ) ; } public static void Main ( ) { string S = " aabccb " ; Console . Write ( waysToClearString ( S ) ) ; } }