Jatayu's Balanced Bracket Sequence
Contest: Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
Difficulty rating: 1300
Tags: data structures, dsu, graphs, greedy

Last summer, Feluda gifted Lalmohan-Babu a balanced bracket sequence $$$s$$$ of length $$$2 n$$$.

Topshe was bored during his summer vacations, and hence he decided to draw an undirected graph of $$$2 n$$$ vertices using the balanced bracket sequence $$$s$$$. For any two distinct vertices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le 2 n$$$), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment $$$s[i \ldots j]$$$ forms a balanced bracket sequence.

Determine the number of connected components in Topshe's graph.

See the Notes section for definitions of the underlined terms.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of opening brackets in string $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$2 n$$$ — a balanced bracket sequence consisting of $$$n$$$ opening brackets "(", and $$$n$$$ closing brackets ")".

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output a single integer — the number of connected components in Topshe's graph.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Sample explanation:

In the first test case, the graph constructed from the bracket sequence (), is just a graph containing nodes $$$1$$$ and $$$2$$$ connected by a single edge.

In the second test case, the graph constructed from the bracket sequence ()(()) would be the following (containing two connected components):

Definition of Underlined Terms:

- A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $$$+$$$ and $$$1$$$. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.
- The subsegment $$$s[l \ldots r]$$$ denotes the sequence $$$[s_l, s_{l + 1}, \ldots, s_r]$$$.
- A connected component is a set of vertices $$$X$$$ such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to $$$X$$$ violates this rule.

Example input:
4
1
()
3
()(())
3
((()))
4
(())(())

Example output:
1
2
3
3

Editorial:
Claim: The answer is one more than the number of occurrences of the substring "((" in the balanced bracket sequence given (considering overlapping occurrences as well).
Proof: Observe the behavior of the lowest index $$$k$$$ of any connected component. The properties that would hold true are:
• $$$s_k = $$$ '('. This is because for all edges connecting indices $$$i$$$ and $$$j$$$ such that $$$i < j$$$, $$$s_i = $$$ '(' and $$$s_j = $$$ ')'.
• $$$k = 1$$$ is the lowest index for its connected component.
• For $$$k > 1$$$, $$$k$$$ is a lowest index for a connected component if and only if $$$s_{k - 1} = $$$ '('. This is because:  if $$$s_{k - 1} = $$$ ')', then for any matching bracket $$$s_{j_1}$$$ of $$$s_{k - 1}$$$ ($$$j_1 < k - 1$$$) and for any matching bracket $$$s_{j_2}$$$ of $$$s_{k}$$$ ($$$j_2 > k$$$), there must be edges $$$(j_1, j_2)$$$ and $$$(k, j_2)$$$. This means that $$$j_1$$$ (which is less than $$$k$$$) is in the connected component of $$$k$$$. [Contradiction]  if $$$s_{k - 1} = $$$ '(', then we can prove that there cannot be a smaller index in the connected component of $$$k$$$. For the sake of contradiction, assume that there exists a smaller index $$$a$$$ in the same connected component. This means, there is an edge $$$(a, b)$$$, such that $$$a < k$$$ and $$$b > k$$$ is in the connected component of $$$k$$$. Let $$$p_i$$$ be the number of '(' minus the the number of ')' in the prefix $$$s[1 \ldots i]$$$ (consider $$$p_0 = 0$$$ for the empty prefix). Observe that for all edges $$$(i, j)$$$, ($$$i < j$$$), it holds that $$$p_j = p_i - 1$$$ and for all $$$i'$$$, $$$i \le i' \le j$$$, we must have $$$p_{i'} \ge p_j$$$. This means that for a connected component $$$\mathcal C$$$, for all $$$i \in \mathcal C$$$, $$$s_i = $$$ '(', $$$p_i$$$ is constant. Hence $$$p_k = p_a$$$. Further we have $$$p_b = p_a - 1$$$ and $$$p_{k - 2} = p_{k - 1} - 1 = p_k - 2 = p_b - 1$$$. This implies $$$a < (k - 1)$$$, hence $$$a \le (k - 2) \le b$$$, however, $$$p_{k - 2} = p_b - 1 < p_b$$$. [Contradiction]
• if $$$s_{k - 1} = $$$ ')', then for any matching bracket $$$s_{j_1}$$$ of $$$s_{k - 1}$$$ ($$$j_1 < k - 1$$$) and for any matching bracket $$$s_{j_2}$$$ of $$$s_{k}$$$ ($$$j_2 > k$$$), there must be edges $$$(j_1, j_2)$$$ and $$$(k, j_2)$$$. This means that $$$j_1$$$ (which is less than $$$k$$$) is in the connected component of $$$k$$$. [Contradiction]
• if $$$s_{k - 1} = $$$ '(', then we can prove that there cannot be a smaller index in the connected component of $$$k$$$. For the sake of contradiction, assume that there exists a smaller index $$$a$$$ in the same connected component. This means, there is an edge $$$(a, b)$$$, such that $$$a < k$$$ and $$$b > k$$$ is in the connected component of $$$k$$$. Let $$$p_i$$$ be the number of '(' minus the the number of ')' in the prefix $$$s[1 \ldots i]$$$ (consider $$$p_0 = 0$$$ for the empty prefix). Observe that for all edges $$$(i, j)$$$, ($$$i < j$$$), it holds that $$$p_j = p_i - 1$$$ and for all $$$i'$$$, $$$i \le i' \le j$$$, we must have $$$p_{i'} \ge p_j$$$. This means that for a connected component $$$\mathcal C$$$, for all $$$i \in \mathcal C$$$, $$$s_i = $$$ '(', $$$p_i$$$ is constant. Hence $$$p_k = p_a$$$. Further we have $$$p_b = p_a - 1$$$ and $$$p_{k - 2} = p_{k - 1} - 1 = p_k - 2 = p_b - 1$$$. This implies $$$a < (k - 1)$$$, hence $$$a \le (k - 2) \le b$$$, however, $$$p_{k - 2} = p_b - 1 < p_b$$$. [Contradiction]
Therefore for each '(' preceded by another '(', we have one such connected component (so we add the occurrences of the substring "((" to our answer). However, we missed the connected component of node $$$1$$$ (so we add $$$1$$$ to our answer). [Proved]
Hence we can solve it in $$$\mathcal O(n)$$$.