Count of ways to empty given String by recursively removing all adjacent duplicates | 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 ] . ; Calculate all Combinations ; Driver Code
var dp = new Array ( 505 ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 505 ) . fill ( - 1 ) ; } var choose = new Array ( 505 ) ; for ( var i = 0 ; i < choose . length ; i ++ ) { choose [ i ] = new Array ( 505 ) . fill ( 0 ) ; } function calc ( l , r , 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 ] ; } let ans = 0 ; for ( let k = l + 1 ; k <= r ; k += 2 ) { let temp = 1 ; if ( s [ l ] == s [ k ] ) { temp = calc ( l + 1 , k - 1 , s ) * calc ( k + 1 , r , s ) * choose [ Math . floor ( ( r - l + 1 ) / 2 ) ] [ Math . floor ( ( r - k ) / 2 ) ] ; ans += temp ; } } return dp [ l ] [ r ] = ans ; } function waysToClearString ( S ) { let n = S . length ; choose [ 0 ] [ 0 ] = 1 ; for ( let i = 1 ; i <= Math . floor ( n / 2 ) ; ++ i ) { choose [ i ] [ 0 ] = 1 ; for ( let j = 1 ; j <= i ; ++ j ) { choose [ i ] [ j ] = ( choose [ i - 1 ] [ j ] + choose [ i - 1 ] [ j - 1 ] ) ; } } return calc ( 0 , n - 1 , S ) ; } let S = " " ; document . write ( waysToClearString ( S ) ) ;