CF 5C - Longest Regular Bracket Sequence

Rating: 1900
Tags: constructive algorithms, data structures, dp, greedy, sortings, strings
Solve time: 1m 21s
Verified: yes

Solution

Problem Understanding

We are given a string made only of ( and ). Among all contiguous substrings, we need to find the maximum length of a substring that forms a valid bracket sequence. We also need to count how many substrings achieve that maximum length.

A valid bracket sequence behaves exactly like correctly matched parentheses in an expression. Every opening bracket must eventually be closed, and no prefix may contain more closing brackets than opening brackets.

The input length can reach 10^6, which completely changes what is feasible. Any algorithm that checks all substrings is impossible. There are roughly n^2 substrings, and even spending constant time per substring would already exceed practical limits. With a 2 second time limit, we should aim for something close to linear time, or at worst O(n log n).

The tricky part is that the longest valid substring is not necessarily the entire valid region between two matching brackets. Invalid characters can split the string into independent segments. For example:

())(())

The correct answer is:

4 1

The substring (()) is valid, but the prefix ())( breaks the sequence. A careless implementation that only counts matched pairs could incorrectly return length 6.

Another easy mistake appears when there are multiple longest substrings:

()()(()())

The correct answer is:

10 1

The whole string is valid, even though smaller valid pieces also exist inside it. Counting every valid segment independently without tracking the maximum properly can overcount.

A particularly important edge case is when no valid substring exists at all:

))))

The output must be:

0 1

The count is 1, not 0. The problem defines this special behavior explicitly.

One more subtle case involves disconnected valid regions of equal size:

()())()

The correct answer is:

4 1

The substring ()() has length 4, while the final () only has length 2. If we reset state incorrectly after an invalid bracket, we may miss the larger segment.

Approaches

The brute-force approach is straightforward. We generate every substring and check whether it forms a valid bracket sequence. Validity can be tested using a balance counter: increment for (, decrement for ), and ensure the balance never becomes negative and ends at zero.

This works logically because every valid bracket sequence satisfies those conditions. The problem is the cost. There are O(n^2) substrings. Even if validity checking is optimized to O(length), the total complexity becomes O(n^3). With n = 10^6, this is astronomically too slow.

We can improve the validity test using prefix balances, but we still cannot afford enumerating all substrings. Even O(n^2) is impossible at this scale.

The key observation is that a valid bracket substring behaves locally. Whenever we encounter a closing bracket, we only care whether there exists an unmatched opening bracket before it. This naturally suggests a stack.

The stack stores indices of unmatched opening brackets. When we see (, we push its index. When we see ), we try to match it with the latest unmatched (.

The deeper insight is how to recover substring lengths efficiently. Suppose position i closes a valid sequence. Then the longest valid substring ending at i starts immediately after the nearest unmatched bracket before it. If we keep the index of the most recent unmatched position on the stack, we can compute lengths in constant time.

This converts the problem from checking every substring independently into processing the string once from left to right.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n³)	O(1)	Too slow
Optimal Stack Solution	O(n)	O(n)	Accepted

Algorithm Walkthrough

Initialize a stack with a single value -1.

This acts as a sentinel. It represents the position before the string starts and allows valid substrings beginning at index 0 to be measured correctly. 2. Maintain two variables:

best_len, the maximum valid substring length found so far.

count, the number of substrings achieving that length. 3. Traverse the string from left to right. 4. If the current character is (, push its index onto the stack.

These indices represent unmatched opening brackets that may later form valid pairs. 5. If the current character is ), pop one element from the stack.

We are attempting to match this closing bracket with the nearest unmatched opening bracket. 6. After popping, check whether the stack became empty.

If it is empty, this ) cannot be matched. Push its index onto the stack as the new boundary of invalidity.

Any future valid substring must start after this position. 7. Otherwise, the stack still contains an index.

Let the current index be i. The length of the valid substring ending at i equals:

i - stack[-1]

The top of the stack now marks the nearest unmatched position before the valid segment. 8. Compare this length with best_len.

If it is larger, update best_len and reset count = 1.

If it is equal, increment count. 9. After processing the entire string, handle the special case where best_len == 0.

The required output becomes 0 1.

Why it works

The stack always stores indices of unmatched brackets. After processing position i, the top of the stack represents the nearest position that prevents extension of a valid substring ending at i.

When a matching pair is formed, removing the matched ( leaves exactly one boundary index before the current valid block. The distance from that boundary to i gives the maximal valid substring ending at i.

Every valid substring is discovered exactly when its right endpoint is processed, and the longest one is measured correctly because unmatched positions partition the string into independent valid regions.

Python Solution

import sys
input = sys.stdin.readline

s = input().strip()

stack = [-1]

best_len = 0
count = 0

for i, ch in enumerate(s):
    if ch == '(':
        stack.append(i)
    else:
        stack.pop()

        if not stack:
            stack.append(i)
        else:
            length = i - stack[-1]

            if length > best_len:
                best_len = length
                count = 1
            elif length == best_len:
                count += 1

if best_len == 0:
    print("0 1")
else:
    print(best_len, count)

The stack begins with -1 because valid substrings may start at index 0. Without this sentinel, a sequence like () would produce length 1 instead of 2.

When processing ), we immediately pop once. This corresponds to consuming either a matching ( or the current invalid boundary. If the stack becomes empty afterward, the current ) has no matching opening bracket. We then store its index as the newest invalid boundary.

The expression:

length = i - stack[-1]

is the core of the algorithm. After a successful match, the top of the stack points to the nearest unmatched index before the current valid block. Subtracting gives the exact substring length.

The order of operations matters. We must pop before checking emptiness. Checking first would incorrectly treat matched brackets as unmatched.

The special output 0 1 is handled separately because no valid substring ever updates count.

Worked Examples

Example 1

Input:

)((())))(()())

i	char	stack after processing	current length	best_len	count
0	)	[0]	-	0	0
1	(	[0, 1]	-	0	0
2	(	[0, 1, 2]	-	0	0
3	(	[0, 1, 2, 3]	-	0	0
4	)	[0, 1, 2]	2	2	1
5	)	[0, 1]	4	4	1
6	)	[0]	6	6	1
7	)	[7]	-	6	1
8	(	[7, 8]	-	6	1
9	(	[7, 8, 9]	-	6	1
10	)	[7, 8]	2	6	1
11	(	[7, 8, 11]	-	6	1
12	)	[7, 8]	4	6	1
13	)	[7]	6	6	2

Final output:

6 2

This trace shows how unmatched closing brackets split the string into separate regions. Index 7 becomes a new boundary after an invalid ).

Example 2

Input:

(()(

i	char	stack after processing	current length	best_len	count
0	(	[-1, 0]	-	0	0
1	(	[-1, 0, 1]	-	0	0
2	)	[-1, 0]	2	2	1
3	(	[-1, 0, 3]	-	2	1

Final output:

2 1

This example demonstrates that unmatched opening brackets remaining in the stack do not invalidate earlier completed substrings.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is pushed and popped at most once
Space	O(n)	The stack may contain all opening bracket indices

With n up to 10^6, linear complexity is exactly what we need. The algorithm performs a constant amount of work per character, and the stack memory usage remains comfortably within limits.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def solve():
    input = sys.stdin.readline

    s = input().strip()

    stack = [-1]

    best_len = 0
    count = 0

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()

            if not stack:
                stack.append(i)
            else:
                length = i - stack[-1]

                if length > best_len:
                    best_len = length
                    count = 1
                elif length == best_len:
                    count += 1

    if best_len == 0:
        print("0 1")
    else:
        print(best_len, count)

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    out = io.StringIO()
    backup = sys.stdout
    sys.stdout = out

    solve()

    sys.stdout = backup
    return out.getvalue().strip()

# provided sample
assert run(")((())))(()())\n") == "6 2", "sample 1"

# minimum size
assert run("(\n") == "0 1", "single opening bracket"

# all invalid
assert run("))))\n") == "0 1", "all closing brackets"

# entire string valid
assert run("(()())\n") == "6 1", "whole string valid"

# multiple maximum substrings
assert run("()()())(()())\n") == "6 1", "largest segment counted once"

# disconnected equal maxima
assert run("()())()()\n") == "4 2", "two longest substrings"

Test input	Expected output	What it validates
`(`	`0 1`	Minimum input size
`))))`	`0 1`	No valid substring exists
`(()())`	`6 1`	Entire string forms one valid sequence
`()()())(()())`	`6 1`	Longest substring spans complex structure
`()())()()`	`4 2`	Multiple longest substrings counted correctly

Edge Cases

Consider the input:

))))

Processing the first character pops the sentinel -1, leaving the stack empty. The algorithm immediately pushes index 0 as the new invalid boundary. The same happens for every remaining character. No valid substring is ever formed, so best_len stays 0. The final special-case handling prints:

0 1

Now consider:

()())()

The algorithm first discovers () with length 2, then ()() with length 4. At index 4, an unmatched ) appears, so the stack resets with boundary 4. The final () has length 2, which does not affect the answer. The output becomes:

4 1

This confirms that invalid brackets correctly separate regions.

Finally, consider:

(()(

The substring () inside the string is valid even though extra opening brackets remain unmatched. After matching index 2, the stack still contains index 0, giving length 2. The final ( remains unmatched but does not erase earlier valid segments. The algorithm correctly outputs:

2 1