Skip to content

Bracket Sequences

A balanced bracket sequence is a string consisting only of characters '(' and ')' such that:

  • 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\) and \(t\) are balanced bracket sequences, then \(st\) is also a balanced bracket sequence.

For example, \((())()\) is a balanced bracket sequence, while \()()\) is not.

Sometimes there are multiple types of brackets, such as \([()]\{\}\). The definition of such variant bracket sequences is similar to that of the simple bracket sequence.

This article will introduce classic problems related to bracket sequences.

Note: In English, the left bracket is generally called an opening bracket, and the right bracket is called a closing bracket.

Checking for Validity

The classic method to determine whether \(s\) is a balanced bracket sequence is based on a greedy approach. This algorithm also applies to variant bracket sequences.

We maintain a stack. For each \(i=1,2,\ldots,|s|\) in order:

  • If \(s_i\) is a closing bracket, the stack is not empty, and the top element of the stack is the corresponding opening bracket for \(s_i\), then pop the top element.
  • Otherwise, push \(s_i\) onto the stack.

After traversing the entire string \(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 the number \(f_n\) of balanced bracket sequences \(s\) of length \(2n\). We can enumerate the position of the bracket that matches \(s_1\), suppose it is \(2i+2\). This divides the entire sequence into two shorter balanced bracket sequences. Therefore,

\[ f_n=\sum_{i=0}^{n-1}f_if_{n-i-1} \]

This is also the recurrence for the Catalan numbers. That is, \(f_n=\frac{1}{n+1}\binom{2n}{n}\).

Of course, the counting method for 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\).

Lexicographically Next Sequence

Given a balanced bracket sequence \(s\), we want to find the next balanced bracket sequence in lexicographic order among all balanced bracket sequences of length \(|s|\). In this problem, we assume that the opening bracket has a smaller lexicographic order than the closing bracket, and variant bracket sequences are not considered.

We need to find the largest index \(i\) such that \(s_i\) is an opening bracket. Then, change it to a closing bracket and reconstruct the suffix \(s[i+1,|s|]\). Additionally, \(i\) must satisfy: the number of opening brackets in \(s[1,i-1]\) is greater than the number of closing brackets.

Suppose after changing \(s_i\) to a closing bracket, the number of opening brackets minus the number of closing brackets in \(s[1,i]\) is \(k\). Then we change the last \(k\) characters of \(s\) to closing brackets, and fill \(s[i+1,|s|-k]\) with the pattern \(((\dots(())\dots))\), because this yields the smallest lexicographic order.

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

Reference Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

Lexicographic Order Computation

Given a balanced bracket sequence \(s\), we want to compute its lexicographic rank.

Consider counting the number of bracket sequences \(p\) that are lexicographically smaller than \(s\).

Suppose \(p_i<s_i\) and \(\forall 1\le j<i,p_j=s_i\). Clearly, \(p_i\) is an opening bracket and \(s_i\) is a closing bracket. Enumerate \(i\) (where \(s_i\) is a closing bracket). Suppose in \(p[1,i]\), the number of opening brackets minus the number of closing brackets is \(k\). Then we need to count the number of bracket sequences of length \(|s|-i\) that have exactly \(k\) unmatched closing brackets and no unmatched opening brackets.

Let \(f(i,j)\) denote the number of bracket sequences of length \(i\) with exactly \(j\) unmatched closing brackets and no unmatched opening brackets.

By enumerating the first character of the bracket sequence, we obtain the recurrence for \(f\): \(f(i,j) = f(i-1,j-1)+f(i-1,j+1)\). The base case is \(f(0,0)=1\). In fact, \(f\) corresponds to OEIS - A053121.

Thus we can compute the lexicographic order in \(O(|s|^2)\).

For variant bracket sequences, the method is similar, except we need to consider for each \(s_i\) all characters that are lexicographically smaller (in the above algorithm, since there is no character smaller than an opening bracket, we only considered the case where \(s_i\) is a closing bracket).

Additionally, using the \(f\) array, we can also find the balanced bracket sequence with a given lexicographic rank \(k\).

This page is mainly translated from the blog post http://e-maxx.ru/algo/bracket_sequences and 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.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用