Maximum Pairs of Bracket Sequences which can be concatenated to form a Regular Bracket Sequence | 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
def countPairs ( N , arr ) : NEW_LINE INDENT open = [ 0 ] * 100 NEW_LINE close = [ 0 ] * 100 NEW_LINE ans = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT c = [ i for i in arr [ i ] ] NEW_LINE d = 0 NEW_LINE minm = 0 NEW_LINE for j in range ( len ( c ) ) : NEW_LINE INDENT if ( c [ j ] == ' ( ' ) : NEW_LINE INDENT d += 1 NEW_LINE DEDENT else : NEW_LINE INDENT d -= 1 NEW_LINE if ( d < minm ) : NEW_LINE INDENT minm = d NEW_LINE DEDENT DEDENT DEDENT if ( d >= 0 ) : NEW_LINE INDENT if ( minm == 0 ) : NEW_LINE INDENT close [ d ] += 1 NEW_LINE DEDENT DEDENT elif ( d < 0 ) : NEW_LINE INDENT if ( minm == d ) : NEW_LINE INDENT open [ - d ] += 1 NEW_LINE DEDENT DEDENT DEDENT ans += close [ 0 ] // 2 NEW_LINE for i in range ( 1 , 100 ) : NEW_LINE INDENT ans += min ( open [ i ] , close [ i ] ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 7 NEW_LINE list = [ ] NEW_LINE list . append ( " ) ( ) ) " ) NEW_LINE list . append ( " ) " ) NEW_LINE list . append ( " ( ( " ) NEW_LINE list . append ( " ( ( " ) NEW_LINE list . append ( " ( " ) NEW_LINE list . append ( " ) " ) NEW_LINE list . append ( " ) " ) NEW_LINE countPairs ( N , list ) NEW_LINE DEDENT