CF 2190B1 - Sub-RBS (Easy Version)
We are given a regular bracket sequence s. A regular bracket sequence (RBS) is one where every prefix contains at least as many '(' as ')', and the total numbers of opening and closing brackets are equal.
CF 2190B1 - Sub-RBS (Easy Version)
Rating: 1400
Tags: combinatorics, constructive algorithms, dp, greedy, strings, two pointers
Solve time: 3m 3s
Verified: no
Solution
Problem Understanding
We are given a regular bracket sequence s. A regular bracket sequence (RBS) is one where every prefix contains at least as many '(' as ')', and the total numbers of opening and closing brackets are equal.
We may delete arbitrary characters from s, keeping the remaining characters in their original order. The resulting string t must also be a non-empty regular bracket sequence.
Among all such subsequences t, we want the maximum possible length such that t is better than s.
The ordering is lexicographic with one extra rule: a longer string is considered larger if the shorter one is its prefix. Since '(' < ')' in the problem's ordering, the first position where the strings differ must have '(' in t and ')' in s.
The input guarantees that s itself is already an RBS. The total length across all test cases is at most 2 · 10^5, which means we need something close to linear time. Any solution that examines many subsequences explicitly is immediately impossible because the number of subsequences is exponential.
The main subtlety is that being a subsequence and being lexicographically larger interact in a non-obvious way.
Consider s = "()".
The only non-empty RBS subsequence is "()" itself. Since it is equal to s, it is not better. The answer is -1.
Consider s = "(())()".
A tempting idea is to remove some characters and make the sequence lexicographically larger. However, every proper RBS subsequence has length at most 4, and none becomes better than the original. The correct answer is -1.
Another easy mistake is to think that any deletion producing a different RBS works. For example:
s = (()(()))
The subsequence "((()))" is valid. At the first differing position, the original has ')' while the subsequence has '(', so it is better. The answer is 6.
The challenge is identifying exactly when such a subsequence exists and maximizing its length.
Approaches
A brute-force approach would enumerate all subsequences of s, check which ones are regular bracket sequences, compare them against s, and keep the longest valid answer.
This is correct because it literally tests every candidate. Unfortunately, a string of length n has 2^n subsequences. Even for n = 60 this is hopeless, while the problem allows a total length of 200000.
We need to exploit the structure of regular bracket sequences.
Since t is a subsequence of s, it can never be longer than s. The only way for t to be better than s is that at some position where they first differ, t contains '(' while s contains ')'.
What does that mean operationally?
Suppose we read both strings from left to right. Before the first difference, the characters must be identical. At the first difference, the next unused character of s is ')', but we skip it and later take some '('.
So the crucial question becomes:
Can we find a ')' in the sequence that is followed somewhere later by a '('?
If such a pattern exists, then at that position we can delete that ')' and continue. The resulting subsequence becomes lexicographically larger.
Now recall a classical property of regular bracket sequences. Every RBS can be uniquely decomposed into primitive blocks. A primitive block is an RBS whose balance returns to zero only at its end.
Examples:
()()() -> () + () + ()
(())() -> (()) + ()
(()(())) -> one primitive block
If the sequence consists of at least two primitive blocks, then there is a boundary between them:
... ) ( ...
A closing bracket of one block is immediately followed, somewhere later, by an opening bracket of the next block.
In that case we can delete exactly one matching primitive block boundary pair and obtain an RBS subsequence of length n - 2 that is better than s.
If the sequence consists of only one primitive block, then every '(' appears before every unmatched closing movement needed to finish the block. There is no way to create the required first difference while keeping an RBS subsequence. No valid answer exists.
So the problem reduces to counting primitive blocks.
If there is exactly one primitive block, answer -1.
If there are at least two primitive blocks, answer n - 2.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(2^n · n) | O(n) | Too slow |
| Optimal | O(n) | O(1) | Accepted |
Algorithm Walkthrough
- Scan the bracket sequence while maintaining the current balance.
- Increase the balance for
'('and decrease it for')'. - Every time the balance becomes zero, a primitive block has ended.
- Count how many times balance reaches zero during the scan. This count equals the number of primitive blocks.
- If the count is exactly one, output
-1.
A single primitive block cannot produce a better regular bracket subsequence.
6. Otherwise output n - 2.
With at least two primitive blocks, we can remove one opening bracket from the beginning of a later block and one matching closing bracket, obtaining an RBS subsequence of length n - 2 that is lexicographically larger than the original.
Why it works
Every regular bracket subsequence of a regular bracket sequence is obtained by deleting matched pairs.
If the sequence has at least two primitive blocks, there exists a boundary where one block ends and another begins. Deleting the outer matching pair of a later block shifts an opening bracket earlier in the comparison, creating the first differing position where the subsequence contains '(' and the original contains ')'. The resulting sequence remains regular and has length n - 2.
No longer subsequence can exist because any proper regular bracket subsequence must delete at least one matched pair, reducing the length by at least two.
When the sequence is a single primitive block, every proper regular bracket subsequence becomes lexicographically smaller than the original. The required first differing position can never have '(' in the subsequence and ')' in the original. Hence no valid subsequence exists.
Python Solution
import sys
input = sys.stdin.readline
def solve():
t = int(input())
ans = []
for _ in range(t):
n = int(input())
s = input().strip()
bal = 0
blocks = 0
for ch in s:
if ch == '(':
bal += 1
else:
bal -= 1
if bal == 0:
blocks += 1
if blocks == 1:
ans.append("-1")
else:
ans.append(str(n - 2))
sys.stdout.write("\n".join(ans))
if __name__ == "__main__":
solve()
The implementation directly follows the structural observation.
The variable bal stores the current bracket balance. Whenever it returns to zero, we have completed one primitive block. Since the input is guaranteed to be an RBS, the balance never becomes negative and finishes at zero.
The key implementation detail is that we count every return to zero, not just the final one. For example:
(())()
The balance reaches zero twice, so there are two primitive blocks. Missing intermediate zeroes would incorrectly classify the sequence.
Once the number of blocks is known, the answer is immediate. A single block gives -1, while multiple blocks give n - 2.
Worked Examples
Example 1
Input:
()
| Position | Character | Balance | Blocks |
|---|---|---|---|
| 1 | ( | 1 | 0 |
| 2 | ) | 0 | 1 |
We finish with exactly one primitive block.
Output:
-1
This demonstrates the smallest possible input. The only RBS subsequence is the entire string itself.
Example 2
Input:
(()(()))
| Position | Character | Balance | Blocks |
|---|---|---|---|
| 1 | ( | 1 | 0 |
| 2 | ( | 2 | 0 |
| 3 | ) | 1 | 0 |
| 4 | ( | 2 | 0 |
| 5 | ( | 3 | 0 |
| 6 | ) | 2 | 0 |
| 7 | ) | 1 | 0 |
| 8 | ) | 0 | 1 |
The balance reaches zero only once.
Output:
-1
The entire sequence is one primitive block, so no better regular bracket subsequence exists.
Example 3
Input:
(())()
| Position | Character | Balance | Blocks |
|---|---|---|---|
| 1 | ( | 1 | 0 |
| 2 | ( | 2 | 0 |
| 3 | ) | 1 | 0 |
| 4 | ) | 0 | 1 |
| 5 | ( | 1 | 1 |
| 6 | ) | 0 | 2 |
There are two primitive blocks.
Output:
4
The maximum length is n - 2 = 4.
This example shows exactly why counting primitive components is sufficient.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | One scan of each string |
| Space | O(1) | Only balance and block counters are stored |
Since the total length over all test cases is at most 2 · 10^5, a linear scan easily fits within the time limit. The memory usage is constant aside from the output buffer.
Test Cases
# helper: run solution on input string, return output string
import sys
import io
def run(inp: str) -> str:
old_stdin = sys.stdin
old_stdout = sys.stdout
sys.stdin = io.StringIO(inp)
out = io.StringIO()
sys.stdout = out
def solve():
input = sys.stdin.readline
t = int(input())
ans = []
for _ in range(t):
n = int(input())
s = input().strip()
bal = 0
blocks = 0
for ch in s:
bal += 1 if ch == '(' else -1
if bal == 0:
blocks += 1
ans.append(str(-1 if blocks == 1 else len(s) - 2))
print("\n".join(ans))
solve()
sys.stdin = old_stdin
sys.stdout = old_stdout
return out.getvalue()
# provided sample
assert run(
"""3
2
()
8
(()(()))
6
(())()
"""
) == "-1\n-1\n4\n"
# minimum size
assert run(
"""1
2
()
"""
) == "-1\n"
# two primitive blocks
assert run(
"""1
4
()()
"""
) == "2\n"
# three primitive blocks
assert run(
"""1
6
()()()
"""
) == "4\n"
# single primitive block
assert run(
"""1
6
((()))
"""
) == "-1\n"
# boundary style case
assert run(
"""1
8
(()())()
"""
) == "6\n"
| Test input | Expected output | What it validates |
|---|---|---|
() |
-1 |
Minimum valid RBS |
()() |
2 |
Exactly two primitive blocks |
()()() |
4 |
Multiple primitive blocks |
((())) |
-1 |
Single primitive block |
(()())() |
6 |
Primitive block followed by another block |
Edge Cases
Single primitive block
Input:
1
8
(()(()))
Balance evolution:
1 2 1 2 3 2 1 0
The balance reaches zero only at the end, so there is exactly one primitive block. The algorithm outputs:
-1
This is correct because every proper regular bracket subsequence becomes lexicographically smaller than the original.
Sequence consisting of many primitive blocks
Input:
1
8
()()()()
Balance reaches zero four times.
The algorithm computes:
blocks = 4
answer = 8 - 2 = 6
Any valid proper regular bracket subsequence must delete at least one matched pair, so length 6 is optimal.
Smallest possible input
Input:
1
2
()
The scan finds exactly one primitive block.
Output:
-1
This verifies that the algorithm handles the minimum boundary correctly without special cases.
Primitive boundary appears only near the end
Input:
1
8
(()())()
The balance sequence is:
1 2 1 2 1 0 1 0
Two primitive blocks are detected. The algorithm returns:
8 - 2 = 6
This confirms that every return to zero must be counted, not only the final one.