'''This solution takes O(n) time and O(1) space

First, let's traverse the string from the beginning to the end and count the number
of opening and closing brackets. As far as we realize that open_counter == close_counter,
we need to recalculate the longest balanced parentheses length (simply it is equal to
the overall number of brackets we've seen so far). If we realize that we've observed more
closing brackets than opening ones, it means that the current subsequence is not valid and
we need to make open_counter = close_counter = 0.

Second, we need to repeat the process, but traverse the string in the opposite direction paying
attention to the fact, that now we consider ')' brackets as 'opening' and '(' as closing.
'''


def traverse_parentheses(parentheses, is_forward):
    '''Returns the length of the longest contiguous substring of balanced parentheses
    after one pass (forward or backward). This function is made to avoid code repetition
    while doing nearly the same during forward and backward parentheses traverse.

    Args:
        parentheses (str): string with brackets (may contain only '(' or ')')
        is_forward (bool): if True we do forward traversing (from first element to the last),
                           otherwise backward traversing (from the last to the first)
    Return:
        int: the length of the longest valid parentheses after the traverse
    '''
    if is_forward:
        open_bracket = '('
        close_bracket = ')'
    else:
        open_bracket = ')'
        close_bracket = '('
        parentheses = parentheses[::-1]

    open_cnt = 0 # counter for opening brackets
    close_cnt = 0 # counter for closing brackets
    longest_parentheses = 0

    for bracket in parentheses:
        if bracket == open_bracket:
            open_cnt += 1
        if bracket == close_bracket:
            close_cnt += 1
        if open_cnt == close_cnt:
            longest_parentheses = max(2 * open_cnt, longest_parentheses)
        elif close_cnt > open_cnt:
            open_cnt = close_cnt = 0

    return longest_parentheses


def get_longest_balanced_parentheses(parentheses):
    '''Returns the length of the longest contiguous substring of balanced parentheses.
    Parentheses are considered balanced when there is a valid closing parenthesis for an opening one.

    Args:
        parentheses (str): string with brackets (may contain only '(' or ')')
    Return:
        int: the length of the longest valid parentheses
    '''
    return max(
        traverse_parentheses(parentheses, True), # forward traversing
        traverse_parentheses(parentheses, False) # backward traversing
    )


# Tests
assert get_longest_balanced_parentheses('()') == 2
assert get_longest_balanced_parentheses('()()') == 4
assert get_longest_balanced_parentheses('(())') == 4
assert get_longest_balanced_parentheses('())') == 2
assert get_longest_balanced_parentheses(')()(') == 2

assert get_longest_balanced_parentheses('') == 0
assert get_longest_balanced_parentheses('))))((((') == 0
assert get_longest_balanced_parentheses('(') == 0
assert get_longest_balanced_parentheses(')') == 0
assert get_longest_balanced_parentheses('(((((') == 0

for n in [100, 1000, 100000]:
    assert get_longest_balanced_parentheses('(' * n + ')' * n) == 2 * n