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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 505 ] [ 505 ] , choose [ 502 ] [ 502 ] ; int calc ( int l , int r , string & s ) { if ( 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 ; } int waysToClearString ( string S ) { memset ( dp , -1 , sizeof ( dp ) ) ; 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 ) ; } int main ( ) { string S = " aabccb " ; cout << waysToClearString ( S ) ; return 0 ; }