Check if a Regular Bracket Sequence can be formed with concatenation of given strings | Function to check possible RBS from the given strings ; Stores the values { sum , min_prefix } ; Iterate over the range ; Stores the total sum ; Stores the minimum prefix ; Check for minimum prefix ; Store these values in vector ; Make two pair vectors pos and neg ; Store values according to the mentioned approach ; Sort the positive vector ; Stores the extra count of open brackets ; No valid bracket sequence can be formed ; Sort the negative vector ; Stores the count of the negative elements ; No valid bracket sequence can be formed ; Check if open is equal to negative ; Driver Code
function checkRBS ( S ) { let N = S . length ; let v = new Array ( N ) ; for ( let i = 0 ; i < N ; ++ i ) { let s = S [ i ] ; let sum = 0 ; let pre = 0 ; for ( let c of s ) { if ( c == " " ) { ++ sum ; } else { -- sum ; } pre = Math . min ( sum , pre ) ; } v [ i ] = [ sum , pre ] ; } let pos = [ ] ; let neg = [ ] ; for ( let i = 0 ; i < N ; ++ i ) { if ( v [ i ] [ 0 ] >= 0 ) { pos . push ( [ - v [ i ] [ 1 ] , v [ i ] [ 0 ] ] ) ; } else { neg . push ( [ v [ i ] [ 0 ] - v [ i ] [ 1 ] , - v [ i ] [ 0 ] ] ) ; } } pos . sort ( ( a , b ) => a - b ) ; let open = 0 ; for ( let p of pos ) { if ( open - p [ 0 ] >= 0 ) { open += p [ 1 ] ; } else { document . write ( " " + " " ) ; return 0 ; } } neg . sort ( ( a , b ) => a - b ) ; let negative = 0 ; for ( let p of neg ) { if ( negative - p [ 0 ] >= 0 ) { negative += p [ 1 ] ; } else { document . write ( " " ) ; return 0 ; } } if ( open != negative ) { document . write ( " " ) ; return 0 ; } document . write ( " " ) ; return 0 ; } let arr = [ " " , " " ] ; checkRBS ( arr ) ;