Number of ways to partition a string into two balanced subsequences | 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
var MAX = 10 ; var F = Array . from ( Array ( MAX ) , ( ) => Array ( MAX ) . fill ( 0 ) ) ; var C = Array ( MAX ) . fill ( 0 ) ; function noOfAssignments ( S , n , i , 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 ] ; } var c_y = C [ i ] - c_x ; if ( S [ 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 ] ; } var S = " " ; var n = S . length ; for ( var i = 0 ; i < MAX ; i ++ ) { for ( var j = 0 ; j < MAX ; j ++ ) { F [ i ] [ j ] = - 1 ; } } C [ 0 ] = 0 ; for ( var i = 0 ; i < n ; ++ i ) { if ( S [ i ] == ' ' ) { C [ i + 1 ] = C [ i ] + 1 ; } else { C [ i + 1 ] = C [ i ] - 1 ; } } document . write ( noOfAssignments ( S , n , 0 , 0 ) + " " ) ;