Maximum Pairs of Bracket Sequences which can be concatenated to form a Regular Bracket Sequence | Java program for the above approach ; Function to count the number of pairs whose concatenation results in the regular bracket sequence ; Stores the count of opening and closing parenthesis for each string arr [ i ] ; Stores maximum count of pairs ; Traverse the array arr [ ] ; Traverse the string c [ ] ; Opening Bracket ; Otherwise , Closing Bracket ; Count of closing brackets needed to balance string ; Count of opening brackets needed to balance string ; Add the count of balanced sequences ; Traverse the array ; Print the resultant count ; Driver Code
import java . io . * ; import java . util . * ; class GFG { static void countPairs ( int N , ArrayList < String > arr ) { int open [ ] = new int [ 100 ] ; int close [ ] = new int [ 100 ] ; int ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { char c [ ] = arr . get ( i ) . toCharArray ( ) ; int d = 0 ; int min = 0 ; for ( int j = 0 ; j < c . length ; j ++ ) { if ( c [ j ] == ' ( ' ) { d ++ ; } else { d -- ; if ( d < min ) min = d ; } } if ( d >= 0 ) { if ( min == 0 ) close [ d ] ++ ; } else if ( d < 0 ) { if ( min == d ) open [ - d ] ++ ; } } ans += close [ 0 ] / 2 ; for ( int i = 1 ; i < 100 ; i ++ ) { ans += Math . min ( open [ i ] , close [ i ] ) ; } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { int N = 7 ; ArrayList < String > list = new ArrayList < String > ( ) ; list . add ( " ) ( ) ) " ) ; list . add ( " ) " ) ; list . add ( " ( ( " ) ; list . add ( " ( ( " ) ; list . add ( " ( " ) ; list . add ( " ) " ) ; list . add ( " ) " ) ; countPairs ( N , list ) ; } }