Zhily and Bracket Swapping

The trick is to stop thinking about the two strings separately for a minute. The operation is per column, so the column type is what actually matters.

Observation 1: only 3 column types matter

For each position $i$, the pair $(a_i,b_i)$ is one of:

• ((
• ))
• mixed: () or )(

Swapping inside a column does:

• nothing for ((
• nothing for ))
• lets you choose which string gets '(' and which gets ')' for a mixed column

So mixed columns are the only flexible ones. Everything else is frozen.

---

Observation 2: the combined prefix balance is fixed

Let $x_i$ be the balance of the first string after the first $i$ columns, and $y_i$ the balance of the second string.

Recall: balance means

$$\text{balance} = \#( - \#)$$

for the prefix.

A column contributes to $x_i+y_i$ as follows:

• (( contributes $+2$
• )) contributes $-2$
• mixed contributes $0$

So if we define

$$p_i = \#\text{`((` in first $i$ columns} - \#\text{`))` in first $i$ columns},$$

then always

$$x_i + y_i = 2p_i.$$

This is completely independent of how we swap mixed columns.

Now, if both final strings are regular bracket sequences, then every prefix in both strings must have nonnegative balance. Hence

$$x_i \ge 0, \qquad y_i \ge 0.$$

Therefore

$$p_i \ge 0 \quad \text{for all } i.$$

Also at the end both balances must be $0$, so

$$p_n = 0.$$

These are obviously necessary.

But they are not sufficient. The all-mixed case has $p_i=0$ forever, yet it's impossible because at position $1$ one of the two strings must start with ')'. Yeah, that’s dead on arrival.

---

Observation 3: when $p_i=0$, both strings must be exactly at balance 0

If

$$p_i = 0,$$

then

$$x_i + y_i = 0.$$

Since both balances must be nonnegative, the only possibility is

$$x_i = y_i = 0.$$

So every prefix where $p_i=0$ is a moment when both strings are back at ground level.

Now look at the difference

$$d_i = x_i - y_i.$$

How does a column affect $d_i$?

• (( changes both balances equally, so $d_i$ does not change
• )) also leaves $d_i$ unchanged
• mixed changes one by $+1$ and the other by $-1$, so $d_i$ changes by $\pm 2$

Therefore, inside any block where we start at $(x,y)=(0,0)$ and later return to $(0,0)$, the number of mixed columns must be even — otherwise $d_i$ cannot return to $0$.

Now here is the neat parity shortcut.

Suppose $p_i=0$. Then in the first $i$ columns, the counts of (( and )) are equal. So among those $i$ columns,

$$i = 2\cdot \#\text{`((`} + \#\text{mixed}.$$

Hence

$$\#\text{mixed} \equiv i \pmod 2.$$

To make the mixed count even, we need

$$i \text{ is even}.$$

So another necessary condition is:

whenever $p_i=0$, the position $i$ must be even.

---

Observation 4: these conditions are also sufficient

This is the real aha.

Take the positions where $p_i=0$. They split the array into segments. In each segment:

• $p$ starts at $0$
• then stays strictly positive inside the segment
• returns to $0$ at the end

Because zeros happen only at even positions, every such segment has even length.

Inside one segment, let the mixed columns be

$$m_1 < m_2 < \dots < m_{2k}.$$

There are an even number of them.

Now orient them in pairs:

• at $m_1$, give '(' to string $a$ and ')' to string $b$
• at $m_2$, do the opposite
• at $m_3$, same as $m_1$
• at $m_4$, same as $m_2$
• and so on

Between $m_{2t-1}$ and $m_{2t}$, one string has balance $p+1$ and the other has $p-1$. Since inside the segment we always have

$$p > 0,$$

we get

$$p-1 \ge 0,$$

so neither string goes negative.

After the second mixed column in the pair, the two balances become equal again. Repeating this for all pairs works for the entire segment.

So the three conditions are not just necessary — they are sufficient.

---

Final criterion

Let each column contribute:

• (( $\to +1$
• )) $\to -1$
• mixed $\to 0$

Let $p$ be the running prefix sum.

The answer is YES iff:

1. $p \ge 0$ for every prefix,
2. $p_n = 0,$
3. whenever $p=0$ at position $i$, that $i$ is even.

That’s it. No DP, no nonsense, no ritual sacrifice to the bracket gods.

---

Complexity

We scan each test case once.

Time complexity:

$$O(n)$$

per test case.

Total over all test cases:

$$O\left(\sum n\right) \le O(2\cdot 10^5).$$

Memory usage:

$$O(1)$$

besides the input strings.