Count all indices of cyclic regular parenthesis | Function to find all indices which cyclic shift leads to get balanced parenthesis ; Create auxiliary array ; Finding prefix sum and minimum element ; Update the minimum element ; ChecK if count of ' ( ' and ' ) ' are equal ; Find count of minimum element ; Find the frequency of mn ; Return the count ; Given string S ; Function call
def countCyclicShifts ( S , n ) : NEW_LINE INDENT aux = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if ( S [ i ] == ' ( ' ) : NEW_LINE INDENT aux [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT aux [ i ] = - 1 NEW_LINE DEDENT DEDENT mn = aux [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT aux [ i ] += aux [ i - 1 ] NEW_LINE mn = min ( mn , aux [ i ] ) NEW_LINE DEDENT if ( aux [ n - 1 ] != 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT count = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT if ( aux [ i ] == mn ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT S = " ) ( ) ( " NEW_LINE N = len ( S ) NEW_LINE print ( countCyclicShifts ( S , N ) ) NEW_LINE