Hints: A Simple RBS Problem
()() into (())? What about (())()into ()(())?
Answer to Hint 1: ()() cannot become (()) — there’s no valid pair of disjoint RBS substrings to swap. But (())() becomes ()(()) by swapping (()) and ().
Think about the bracket matching of an RBS: each ( is matched to a unique ). Consider the “bracket tree” where each matched pair is a node, and pair $A$ is the parent of pair $B$ if $A$ is the innermost pair containing $B$. The leaves of this tree are atoms — the () pairs that contain nothing inside. Can a swap change the number of atoms?
Answer to Hint 2: No. Every RBS starts with ( and ends with ). So when you swap two disjoint RBS substrings, the boundary characters are preserved: before each swapped region you still see the same character, and after each region likewise. No adjacent () pair is created or destroyed at any boundary. Atoms inside each swapped region and in the unswapped parts are merely rearranged.
So the atom count (number of () substrings) is an invariant. Is there another invariant?
Answer to Hint 3: Consider the outer nesting depth: the number of concentric matched pairs that wrap the entire string. For example, ((())) has depth 3, (()()) has depth 1, and ()() has depth 0. You can compute this by checking whether position $0$ matches position $n-1$, then whether position $1$ matches $n-2$, and so on.
Can a swap operation change this depth?
Answer to Hint 4: No. If position $0$ is ( matched to position $n-1$ which is ), then any RBS substring that contains position $0$ must also contain its match at position $n-1$ — making it the entire string. Since a valid swap requires two disjoint non-empty RBS substrings, neither can be the full string. So position $0$ and $n-1$ can’t participate in any swap, and the outermost wrapping pair is preserved. By induction on depth, the outer nesting depth is invariant.
You now have two invariants. Are they sufficient?
Answer to Hint 5: Yes — two RBS strings can be transformed into each other if and only if they share both invariants.
For sufficiency, argue that any RBS with outer depth $d$ and atom count $k$ can be reduced to the canonical form: $d$ nested wrapping pairs around $k$ adjacent atoms, i.e., $\underbrace{(\cdots(}{d};\underbrace{(),(),\cdots,()}{k};\underbrace{)\cdots)}_{d}$.
Why? After stripping $d$ outer layers (which are untouched by swaps), you have an RBS of depth $0$. A depth-0 RBS is a concatenation of “primitive” blocks of the form $(X)$. These blocks can be freely reordered by swapping pairs of them. And within each block $(X)$, the inner RBS $X$ can be recursively simplified the same way.
Answer to Hint 6: So the algorithm is: compute both invariants for $s$ and $t$, and output YES iff they match.
Outer depth: match brackets (using a stack), then check from both ends: while position $\ell$ is matched to position $r$, increment depth and move inward ($\ell{+}{+}$, $r{-}{-}$).
Atom count: scan for adjacent () pairs, i.e., count positions $i$ where $s[i] =$ ( and $s[i+1] =$ ).
What is the time complexity?