Building Bracket Strings

Let $S_i$ be the balance of the first $i$ characters. An interval $[l,r]$ is regular exactly when

$$S_{l-1}=S_r,\qquad S_j\geq S_{l-1}\quad(l\leq j\leq r).$$

Treat boundaries $0,\ldots,N$ as vertices and unite $l-1,r$ for every required interval using a DSU.

Also merge components whose boundaries alternate as $x_1<y_1<x_2<y_2$. To do so, scan boundaries left to right, keeping active components on a stack. Whenever a component reappears, merge all components above it into it. Remove a component upon reaching its last boundary.

Consecutive boundaries of the resulting components define intervals that are disjoint or nested. Remove each interval's immediate children and concatenate its remaining positions in order. Make every residual group regular independently. At positions outside all intervals, take $\max(a_i,b_i)$.

To optimize a group of length $2k$, initially use only closing brackets, earning $\sum b_i$. Changing position $i$ to an opening bracket gains $a_i-b_i$. Scan the group, inserting these gains into a max-heap. At each odd position, extract the largest gain and select that position as an opening bracket.

The groups contain at most $N$ positions altogether. Total time is $O((N+M)\alpha(N)+N\log N)$ and space is $O(N+M)$, where is the inverse Ackermann function.

Proof

Boundaries in one DSU component have equal heights. Its original intervals cover the component's span without dropping below this common height, so substrings between consecutive boundaries must be regular. If two components cross, their prefix conditions force each component's height to be at least the other's. Their heights are equal, so merging them preserves the constraints.

After resolving all crossings, intervals are disjoint or nested. Inserting or deleting a regular substring preserves the outer string's regularity. Thus, the original constraints are equivalent to requiring every residual group to be regular independently.

Within a group, the first $2j-1$ positions need at least $j$ openings. An optimum containing the previous greedy choices must select an additional position in this prefix. Exchange that selection for the largest available gain. Earlier prefix requirements are already satisfied by previous choices; later prefixes contain both exchanged positions. Feasibility is preserved and reward cannot decrease, proving optimality.