Double Bracket Sequence

Research basis: I checked the official Codeforces editorial/solution, the accepted submissions status page, and independent explanations by Daniel Z and kmjp. They all point to the same core idea: delete already-good same-type pairs, then solve a tiny parity problem on the leftovers.

A useful rephrase: a beautiful string is equivalent to partitioning all positions into pairs (i, j) with i < j, and coloring each pair round or square. The left endpoint becomes the opening bracket of that color, and the right endpoint becomes the closing bracket. For each color, every close has its own earlier open, so the subsequence is correct. Conversely, any correct bracket subsequence can be matched this way.

Now look at the cost of one pair. If the original two characters are already () or [], the pair costs $0$. If not, then the pair costs $1$ unless the left character is a closing bracket and the right character is an opening bracket. That cursed orientation costs $2$, because both endpoints must flip direction. So relative to the normal cost $1$, free same-type pairs save one operation, and closing-opening pairs add one operation.

First, take all free pairs we can. For each type independently, scan the string with a stack: push opens, and when a matching close appears, pop one open; otherwise the close stays unmatched. This is exactly the standard greedy maximum matching for a bracket subsequence, so it finds the maximum number of original () pairs and original [] pairs that can remain unchanged.

Why is this safe? A skipped free pair can save at most one later bad-pair penalty, but skipping it already loses one zero-cost saving, so it never improves the answer. Among maximum choices, the stack version is also the extremal useful one: unmatched opens are as early as possible, and unmatched closes are as late as possible. Therefore, if this leftover string has no opening before a later closing, no other maximum deletion can magically create one. No DP, no flow, no 2500-rated ritual sacrifice.

Let $V$ be the leftover string after those stack deletions. Let $m = |V|$, open be the number of ( or [ in $V$, and close be the number of ) or ] in $V$. Since all zero-cost pairs are gone, every remaining pair costs at least $1$, so the base lower bound is $m/2$.

When can we achieve exactly $m/2$?

If open and close are both even, pair openings with openings and closings with closings. An opening-opening pair keeps the left endpoint; a closing-closing pair keeps the right endpoint. Every pair costs $1$.

If both counts are odd, same-orientation pairing leaves one opening and one closing. If $V$ contains an opening before a later closing, then there is an adjacent opening-closing transition somewhere in $V`; pair those two together for cost$1`, and now both remaining counts are even. Again the total is $m/2$.

The only bad case is: both counts are odd, and no opening appears before a closing. Then $V$ must look like all closings first, then all openings: closings* openings*. Since both counts are odd, at least one mixed-orientation pair is forced. But every mixed pair is then closing-opening, so it costs $2$ instead of $1$. This adds exactly one extra operation, and one such bad pair is enough.

So the answer is:

m / 2 + 1 only if open and close are odd and there is no opening-closing transition in the leftover string. Otherwise it is just m / 2.

Implementation details:

Run the stack deletion twice, once for (, ) and once for [, ]. Mark every unmatched position. Then scan only marked positions. Count openings and closings, and detect whether a marked closing immediately follows a marked opening. In a binary orientation string, having any opening before any later closing is equivalent to having some adjacent opening-closing transition, so this check is enough.

The complexity is $O(n)$ per test case and $O(n)$ memory. Over all tests, this is $O(sum n)$, which fits easily.