Count of ways to empty given String by recursively removing all adjacent duplicates | Java program 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 Initialize all the states of dp to - 1 ; Calculate all Combinations ; Driver Code
import java . io . * ; 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 . charAt ( l ) == s . charAt ( 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 . charAt ( l ) == s . charAt ( 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 [ ] args ) { String S = " aabccb " ; System . out . println ( waysToClearString ( S ) ) ; } }