Number of ways to partition a string into two balanced subsequences | Java implementation of the approach ; For maximum length of input string ; Declaring the DP table ; Declaring the prefix array ; Function to calculate the number of valid assignments ; Return 1 if X is balanced . ; Increment the count if it an opening bracket ; Decrement the count if it a closing bracket ; Driver code ; Initializing the DP table ; Creating the prefix array ; Initial value for c_x and c_y is zero
public class GFG { static int MAX = 10 ; static int F [ ] [ ] = new int [ MAX ] [ MAX ] ; static int C [ ] = new int [ MAX ] ; static int noOfAssignments ( String S , int n , int i , int c_x ) { if ( F [ i ] [ c_x ] != - 1 ) { return F [ i ] [ c_x ] ; } if ( i == n ) { if ( c_x == 1 ) { F [ i ] [ c_x ] = 0 ; } else { F [ i ] [ c_x ] = 1 ; } return F [ i ] [ c_x ] ; } int c_y = C [ i ] - c_x ; if ( S . charAt ( i ) == ' ( ' ) { F [ i ] [ c_x ] = noOfAssignments ( S , n , i + 1 , c_x + 1 ) + noOfAssignments ( S , n , i + 1 , c_x ) ; return F [ i ] [ c_x ] ; } F [ i ] [ c_x ] = 0 ; if ( c_x == 1 ) { F [ i ] [ c_x ] += noOfAssignments ( S , n , i + 1 , c_x - 1 ) ; } if ( c_y == 1 ) { F [ i ] [ c_x ] += noOfAssignments ( S , n , i + 1 , c_x ) ; } return F [ i ] [ c_x ] ; } public static void main ( String [ ] args ) { String S = " ( ) " ; int n = S . length ( ) ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { F [ i ] [ j ] = - 1 ; } } C [ 0 ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( S . charAt ( i ) == ' ( ' ) { C [ i + 1 ] = C [ i ] + 1 ; } else { C [ i + 1 ] = C [ i ] - 1 ; } } System . out . println ( noOfAssignments ( S , n , 0 , 0 ) ) ; } }