Check if a Regular Bracket Sequence can be formed with concatenation of given strings | Java program for the above approach ; 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int checkRBS ( String [ ] S ) { int N = S . length ; pair [ ] v = new pair [ N ] ; for ( int i = 0 ; i < N ; ++ i ) { String s = S [ i ] ; int sum = 0 ; int pre = 0 ; for ( char c : s . toCharArray ( ) ) { if ( c == ' ( ' ) { ++ sum ; } else { -- sum ; } pre = Math . min ( sum , pre ) ; } v [ i ] = new pair ( sum , pre ) ; } Vector < pair > pos = new Vector < pair > ( ) ; Vector < pair > neg = new Vector < pair > ( ) ; for ( int i = 0 ; i < N ; ++ i ) { if ( v [ i ] . first >= 0 ) { pos . add ( new pair ( - v [ i ] . second , v [ i ] . first ) ) ; } else { neg . add ( new pair ( v [ i ] . first - v [ i ] . second , - v [ i ] . first ) ) ; } } Collections . sort ( pos , ( a , b ) -> a . first - b . first ) ; int open = 0 ; for ( pair p : pos ) { if ( open - p . first >= 0 ) { open += p . second ; } else { System . out . print ( " No " + "NEW_LINE"); return 0 ; } } Collections . sort ( neg , ( a , b ) -> a . first - b . first ) ; int negative = 0 ; for ( pair p : neg ) { if ( negative - p . first >= 0 ) { negative += p . second ; } else { System . out . print ( "NoNEW_LINE"); return 0 ; } } if ( open != negative ) { System . out . print ( "NoNEW_LINE"); return 0 ; } System . out . print ( "YesNEW_LINE"); return 0 ; } public static void main ( String [ ] args ) { String [ ] arr = { " ) " , " ( ) ( " } ; checkRBS ( arr ) ; } }