Longest Regular Bracket Sequence (Codeforces 5C)
Tags: Greedy, sortings

This is yet another problem dealing with regular bracket sequences.We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not. You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

Input: The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Output: Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".


Sample Inputs:
)((())))(()())

))(

Sample Outputs:
6 2

0 1

Solution (Python):
def longest_regular_substring(s):
    stack = []
    max_len = 0
    count = 1
    start = 0
    for (i, c) in enumerate(s):
        if c == '(':
            stack.append(i)
        elif stack:
            stack.pop()
            if stack:
                length = i - stack[-1]
            else:
                length = i - start + 1
            if length > max_len:
                max_len = length
                count = 1
            elif length == max_len:
                count += 1
        else:
            start = i + 1
    return (max_len, count)
s = input()
print(*longest_regular_substring(s))

Solution (Python):
def find_longest_substring(brackets):
    stack = []
    max_length = 0
    count = 0
    for (i, bracket) in enumerate(brackets):
        if bracket == '(':
            stack.append(i)
        elif stack and brackets[stack[-1]] == '(':
            stack.pop()
            length = i - (stack[-1] if stack else -1)
            if length > max_length:
                max_length = length
                count = 1
            elif length == max_length:
                count += 1
        else:
            stack.append(i)
    if count == 0:
        return '0 1'
    else:
        return f'{max_length} {count}'
brackets = input()
result = find_longest_substring(brackets)
print(result)

Solution (Python):
line = input()
s = [-1]
max_len = 0
max_num = 1
l = len(line)
for i in range(l):
    if line[i] == '(':
        s.append(i)
    elif len(s) > 1:
        s.pop()
        n = i - s[-1]
        if max_len < n:
            (max_len, max_num) = (n, 1)
        elif max_len == n:
            max_num += 1
    else:
        s[0] = i
print(str(max_len) + ' ' + str(max_num))