Balanced bracket sequences

A balanced bracket sequence is a string consisting only of $($ and $)$ and satisfying the following conditions:

• The empty string $\varepsilon$ is a balanced bracket sequence.
• If $s$ is a balanced bracket sequence, then $(s)$ is also a balanced bracket sequence.
• If $s,t$ are both balanced bracket sequences, then $st$ is also a balanced bracket sequence.

For example, $(())()$ is a balanced bracket sequence, whereas $)()$ is not.

Sometimes there are multiple kinds of brackets, such as $[()]\{\}$. Such variant bracket sequences have definitions similar to those of ordinary bracket sequences.

This article introduces classic problems related to bracket sequences.

Note: in English, a left bracket is generally called an opening bracket, while a right bracket is called a closing bracket.

Checking validity

The classic way to determine whether $s$ is a balanced bracket sequence is based on a greedy idea. The same algorithm also applies to variant bracket sequences.

We maintain a stack and consider $i=1,2,\ldots,|s|$ in order:

• If $s_i$ is a right bracket, the stack is nonempty, and the top element of the stack is the left bracket corresponding to $s_i$, pop the top element.
• If the above conditions are not met, push $s_i$ onto the stack.

After traversing the entire $s$, if the stack is empty, then $s$ is a balanced bracket sequence; otherwise, it is not. The time complexity is $O(n)$.

Counting balanced bracket sequences

Consider finding, for length $2n$, the number of balanced bracket sequences $s$; call this number $f_n$. We may enumerate the position of the bracket matching $s_1$; suppose it is $2i+2$. It divides the entire sequence into two shorter balanced bracket sequences. Therefore,

This is also the recurrence for the Catalan numbers. In other words, $f_n=\frac{1}{n+1}\binom{2n}{n}$.

Naturally, the method for counting variant balanced bracket sequences is similar. Suppose there are $k$ different types of brackets; then $f'_n=\frac{1}{n+1}\binom{2n}{n}k^n$.

Lexicographic successor

Given a balanced bracket sequence $s$, we want to find, among all valid bracket sequences of length $|s|$ sorted in ascending lexicographic order, the next valid bracket sequence after $s$. In this problem, we regard the lexicographic order of a left bracket as smaller than that of a right bracket, and do not consider variant bracket sequences.

We need to find the largest $i$ such that $s_i$ is a left bracket. Then change it into a right bracket and reconstruct the part $s[i+1,|s|]$. In addition, $i$ must satisfy the condition that the number of left brackets in $s[1,i-1]$ is greater than the number of right brackets.

Suppose that after $s_i$ is changed into a right bracket, the number of left brackets in $s[1,i]$ exceeds the number of right brackets by $k$. Then we make $s$'s last $k$ characters right brackets, and fill $s[i+1,|s|-k]$ in the form $((\dots(())\dots))$, because this filling gives the smallest lexicographic order.

The time complexity of this algorithm is $O(n)$.

bool next_balanced_sequence(string& s) {
  int n = s.size();
  int depth = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == '(')
      depth--;
    else
      depth++;

    if (s[i] == '(' && depth > 0) {
      depth--;
      int open = (n - i - 1 - depth) / 2;
      int close = n - i - 1 - open;
      string next =
          s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
      s.swap(next);
      return true;
    }
  }
  return false;
}

Computing lexicographic rank

Given a balanced bracket sequence $s$, we want to find its lexicographic rank.

Consider finding, relative to $s$, the number of bracket sequences $p$ that are lexicographically smaller.

Suppose that $p_i<s_i$ and $\forall 1\le j Its English translation Balanced bracket sequences. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.**