Sub-RBS (Easy Version)

Because $t$ is a subsequence of $s$, we always have $|t| \le n$. So the first rule for being better, where $s$ is a proper prefix of $t$, cannot happen. The only possible win is lexicographic: at the first position where $t$ and $s$ differ, $t$ must have ( and $s$ must have ).

The length-$n$ subsequence of $s$ is only $s$ itself, and it is not better than itself. Also, every regular bracket sequence has the same number of ( and ). Therefore any valid better subsequence must delete at least one opening bracket and one closing bracket, so the maximum possible answer is at most

$$n-2.$$

Now we prove exactly when this upper bound is achievable.

Suppose there is a ) in $s$ with at least two ( characters after it. In other words, $s$ contains )(( as a subsequence. Let:

$$i < j < k, \qquad s_i=\texttt{)},\ s_j=\texttt{(},\ s_k=\texttt{(},$$

and choose $j$ to be the first ( after $i$. Build $t$ by deleting positions $i$ and $k$.

The length is clearly $n-2$, and the total balance is still $0$ because we deleted one ) and one (.

Why is $t$ still regular? Deleting the earlier ) increases all affected prefix balances by $1$. Later, deleting the ( at $k$ decreases the balance back by $1$. So no prefix balance ever becomes smaller than the corresponding prefix balance in $s$. Since $s$ was regular, $t$ is regular too. Nice, no hidden nonsense.

Why is $t$ better than $s$? Since $j$ is the first ( after $i$, all characters from $i$ to $j-1$ are ). After deleting $s_i$, those ) characters just shift left and still match $s$ for a while. Then $s_j=\texttt{(}$ shifts into a position where $s$ still has ). That is the first difference, and it is exactly the good kind: $t$ has ( while $s$ has ).

So if )(( is a subsequence, answer $n-2$.

Now prove the other direction. Assume a better regular subsequence $t$ exists, and let $q$ be the first position where $t_q \ne s_q$. Then

$$s_q=\texttt{)}, \qquad t_q=\texttt{(}.$$

That ( in $t_q$ must come from some position after $q$ in $s$, so there is at least one ( after $q$.

There must actually be at least two. If there were only one ( after $q$, then the first $q$ characters of $t$ would already use every opening bracket of $s$: the first $q-1$ characters match $s_1,\dots,s_{q-1}$, and $t_q$ uses the only later opening bracket. Since $t$ is a proper subsequence, it deletes something. But if it deletes no opening bracket, it deletes only closing brackets, so its numbers of ( and ) cannot be equal. That is impossible for a regular bracket sequence.

Therefore $s_q=\texttt{)}$ has at least two ( characters after it. So )(( must be a subsequence.

The algorithm is now tiny:

Scan from right to left and keep $opensRight$, the number of ( characters strictly to the right of the current position. If we ever see a ) with $opensRight \ge 2$, print $n-2$. Otherwise print $-1$.

Complexity is

$$O(n)$$

per test case and $O(1)$ extra memory. Across all tests, this is $O(\sum n)$.