A Simple RBS Problem

Turn the RBS into a tree

Take a string $x$ and wrap it as ( + $x$ + ). Now every bracket pair is a node, and the nearest enclosing bracket pair is its parent. The added pair is the root.

The key translation is:

$\text{RBS substring} \iff \text{a consecutive block of children of one node}.$

So the operation becomes: choose two disjoint contiguous child-blocks, possibly under different parents, and swap those blocks. That's the whole damn problem after the disguise comes off.

Invariant 1: leaves

A swap moves entire subtrees. It never opens a subtree and rearranges its insides. Also, the two parent nodes involved exchange non-empty child-blocks, so an internal node never becomes a leaf.

Therefore the number of leaves is invariant. In the string, a leaf is exactly an adjacent pair $\texttt{()}$, so

$L(x)=|\{i \mid x_i x_{i+1}=\texttt{()}\}|.$

Invariant 2: the forced top chain

Define $H(x)$ like this: starting from the whole string, while the first bracket matches the last bracket, strip that outer pair and add $1$.

In the wrapped tree, $H(x)$ is the length of the initial chain below the root where every node has exactly one child. Equivalently, it is the depth of the first node whose number of children is not $1$.

Why is $H$ invariant? Every node on that initial chain has only one child, and that child contains everything below it. There is no disjoint RBS block outside that child subtree, so swaps cannot affect this chain. If the first non-unary node is branching, it also cannot become unary: to reduce it to one child, we would need to swap all its children with some disjoint single block outside them, but outside them there is nothing useful. If the whole tree is just a chain, no operation exists at all.

So both $L$ and $H$ are necessary.

Why these invariants are sufficient

Now suppose two strings have the same $L$ and $H$. If $L=1$, the tree is just one chain, so it is already uniquely determined. Boring, but correct.

Otherwise, let $u$ be the first branching node, at depth $H$. The chain above $u$ is fixed, so we only care about the subtree below $u$.

First, make $u$ have exactly $L$ children. Suppose $d=\deg(u)<L$. Then some descendant $v$ must be branching; otherwise each child of $u$ would be a chain and there would be exactly $d$ leaves. Choose a child $a$ of $u$ that is not an ancestor of $v$; this exists because $u$ is branching. Swap the one-subtree block $a$ with the whole child-list of $v$.

Then

$\deg(u) \to \deg(u)-1+\deg(v),$

which strictly increases. It also cannot exceed $L$, because every child of $u$ must contain at least one leaf. Repeat until $\deg(u)=L$.

At that point, each child of $u$ contains exactly one leaf, so every child subtree is just a chain. Pick one child of $u$ as the collector. For every other child that is not already a leaf, swap that whole child subtree with the bottom leaf of the collector chain. This makes the other child position a leaf and moves its extra length into the collector chain.

The final canonical tree is unique:

• the first $H$ levels are a forced chain;
• the node $u$ has $L$ children;
• $L-1$ of them are leaves;
• the remaining child is one long chain containing all leftover nodes.

If the wrapped tree has

$N=\frac n2+1$

nodes, that collector chain has length

$N-H-L.$

Thus every tree with the same pair $(L,H)$ can reach the same canonical tree. Since every operation is reversible, if $s$ and $t$ have the same $(L,H)$, then

$s \to \text{canonical} \to t.$

So the answer is exactly whether these two invariants match.

Implementation

Compute $L$ by counting adjacent $\texttt{()}$.

Compute $H$ by matching brackets with a stack, then repeatedly checking whether the current leftmost opening bracket matches the current right endpoint.

The total complexity is

$O\left(\sum n\right)$

time and $O(n)$ memory per test case.

Reference checked while preparing this explanation: official Codeforces editorial.