CF 2110B - Down with Brackets

CF 2110B - Down with Brackets

Rating: 900
Tags: strings
Solve time: 1m 8s
Verified: yes

Solution

Problem Understanding

We are given a string representing a balanced sequence of parentheses, and we need to decide whether it is possible to remove exactly one opening bracket and exactly one closing bracket such that the resulting string is no longer balanced. A balanced sequence follows the usual rules: every opening bracket has a matching closing bracket, and the brackets are properly nested.

The input consists of multiple test cases, and each string is guaranteed to be balanced. The length of each string can be up to 200,000, and the sum of all strings across all test cases also does not exceed 200,000. This implies that we must solve each test case in roughly linear time relative to the string length, since quadratic or cubic algorithms would be too slow.

The smallest possible balanced sequences are "()" and "((...))", which gives us insight into edge cases. For instance, a sequence like "()" cannot be broken by removing one opening and one closing bracket: removing both would leave the empty string, which is still balanced. Similarly, sequences that are perfectly nested without concatenation of separate balanced blocks, like "(())", also cannot be broken by removing one of each type of bracket. On the other hand, sequences that consist of concatenated balanced subsequences, like "(())()()", can be broken by removing the last opening and first closing bracket of adjacent blocks.

The non-obvious edge case occurs when the sequence is a single nested block, like "(())", where removing one opening and one closing bracket from different positions cannot create an imbalance. Naively trying random removals may suggest it can be broken, but careful examination shows it cannot.

Approaches

A brute-force approach would consider every pair of one opening bracket and one closing bracket, remove them, and check if the resulting string is balanced. Checking balance requires scanning the string and maintaining a counter of net open brackets. This approach is correct, but for a string of length $n$, it would involve $O(n^3)$ operations in the worst case: $O(n^2)$ pairs and $O(n)$ to verify balance. With $n$ up to 200,000, this is infeasible.

The key observation is that a balanced sequence can only resist being broken if it is a perfectly nested single block without concatenation. If the first half of the sequence is all openings and the second half all closings, removing one opening from the start and one closing from the end still leaves a balanced sequence. This structure is equivalent to a string of the form "((...))" with no concatenation. Any other balanced sequence has at least two "blocks" that are adjacent; removing the last opening of the first block and the first closing of the next block creates an imbalance, so it can be broken.

Thus, the problem reduces to checking whether the sequence is a perfectly nested block. If it is, output "NO"; otherwise, output "YES".

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n^3)	O(n)	Too slow
Optimal	O(n)	O(1)	Accepted

Algorithm Walkthrough

1. For each test case, read the string $s$. The string is guaranteed to be balanced, so the number of opening brackets equals the number of closing brackets.
2. Count the number of consecutive opening brackets from the start of the string until the first closing bracket. Call this prefix_open.
3. Count the number of consecutive closing brackets from the end of the string backward until the first opening bracket. Call this suffix_close.
4. Compare prefix_open + suffix_close to the total length of the string. If they equal the string length, it means all the opening brackets are at the start and all closing brackets are at the end. This is a single nested block.
5. If it is a single nested block, output "NO" because removing one opening and one closing bracket anywhere will still leave a balanced sequence. Otherwise, output "YES" because there is at least one way to remove brackets from two adjacent blocks and break the balance.

Why it works: The invariant here is that a balanced sequence that is not a single nested block contains at least one boundary between two blocks. Removing one bracket from the end of one block and one from the start of the next always produces an unmatched bracket, breaking the balance. Conversely, a single nested block cannot be broken with exactly one of each type of bracket.

Python Solution

import sys
input = sys.stdin.readline

def main():
    t = int(input())
    for _ in range(t):
        s = input().strip()
        n = len(s)
        prefix_open = 0
        while prefix_open < n and s[prefix_open] == '(':
            prefix_open += 1
        suffix_close = 0
        while suffix_close < n and s[n - 1 - suffix_close] == ')':
            suffix_close += 1
        if prefix_open + suffix_close == n:
            print("NO")
        else:
            print("YES")

if __name__ == "__main__":
    main()

The first loop counts the initial consecutive opening brackets. The second loop counts the trailing consecutive closing brackets. Comparing their sum to the total length directly checks for the single nested block structure. Edge cases, like "()" or "((()))", are handled correctly because in those cases prefix_open + suffix_close equals the length of the string, producing the correct "NO".

Worked Examples

Sample Input 1: "(())"

i	prefix_open	suffix_close	prefix_open + suffix_close	Output
0	2	2	4	NO

The trace shows that all openings are at the start and all closings at the end, forming a single block. Removing one of each does not break balance.

Sample Input 2: "(())()()"

i	prefix_open	suffix_close	prefix_open + suffix_close	Output
0	2	2	4	YES

Here, the string is not a single block. There is a concatenation of two balanced subsequences. Removing one opening from the second block and one closing from the first block breaks the sequence, so output is "YES".

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each test case requires two linear scans to count prefix and suffix brackets.
Space	O(1)	Only integer counters are needed. No additional storage proportional to n.

Given the sum of all string lengths does not exceed 200,000, this algorithm comfortably runs in under 1 second and uses negligible memory.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    out = io.StringIO()
    sys.stdout = out
    main()
    return out.getvalue().strip()

# provided samples
assert run("4\n(())\n(())()()\n()\n(())(())\n") == "NO\nYES\nNO\nYES", "sample 1"

# minimum-size input, cannot break
assert run("1\n()\n") == "NO", "minimum size"

# maximum-size nested block, cannot break
assert run(f"1\n{'(' * 100000 + ')' * 100000}\n") == "NO", "max size nested block"

# two concatenated blocks, can break
assert run(f"1\n{'(' * 50000 + ')' * 50000 + '(' * 50000 + ')' * 50000}\n") == "YES", "max size concatenated"

# single pair with surrounding blocks, can break
assert run("1\n()()()\n") == "YES", "multiple small blocks"

# alternating brackets, can break
assert run("1\n()()()()\n") == "YES", "alternating blocks"

Test input	Expected output	What it validates
"()"	NO	Minimum-length sequence
100000 '(' + 100000 ')'	NO	Maximum-size single block
50000 '(' + 50000 ')' + 50000 '(' + 50000 ')'	YES	Maximum-size concatenated blocks
"()()()"	YES	Multiple small blocks
"()()()()"	YES	Alternating brackets, breakable

Edge Cases

For "()", the algorithm counts prefix_open = 1 and suffix_close = 1. Their sum equals 2, which is the length of the string, so it outputs "NO" correctly. For a large nested block, such as 100,000 '(' followed by 100,000 ')', the counters correctly detect a single nested block and return "NO". For concatenated blocks, like "(())()()", the sum of prefix and suffix is smaller than the total length, triggering "YES", demonstrating the algorithm handles boundaries between blocks correctly.