Number of balanced bracket expressions that can be formed from a string | Max string length ; Function to check whether index start and end can form a bracket pair or not ; Check for brackets ( ) ; Check for brackets [ ] ; Check for brackets { } ; Function to find number of proper bracket expressions ; If starting index is greater than ending index ; If dp [ start ] [ end ] has already been computed ; Search for the bracket in from next index ; If bracket pair is formed , add number of combination ; If ? comes then all three bracket expressions are possible ; Return answer ; If n is odd , string cannot be balanced ; Driving function
let MAX = 300 ; function checkFunc ( i , j , st ) { if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; if ( st [ i ] == ' ' && st [ j ] == ' ' ) return 1 ; return 0 ; } function countRec ( start , end , dp , st ) { let sum = 0 ; if ( start > end ) return 1 ; if ( dp [ start ] [ end ] != - 1 ) return dp [ start ] [ end ] ; let i , r = 0 ; for ( i = start + 1 ; i <= end ; i += 2 ) { if ( checkFunc ( start , i , st ) == 1 ) { sum = sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) ; } else if ( st [ start ] == ' ' && st [ i ] == ' ' ) { sum = sum + countRec ( start + 1 , i - 1 , dp , st ) * countRec ( i + 1 , end , dp , st ) * 3 ; } } return dp [ start ] [ end ] = sum ; } function countWays ( st ) { let n = st . length ; if ( n % 2 == 1 ) return 0 ; let dp = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { dp [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) dp [ i ] [ j ] = - 1 ; } return countRec ( 0 , n - 1 , dp , st ) ; } let st = " " ; document . write ( countWays ( st ) ) ;