Range Queries for Longest Correct Bracket Subsequence in C++

In this tutorial, we will look at how to find the longest correct bracket subsequence for a range. We implement this in C++.

Bracket sequences are character arrays consisting of only the characters ‘(‘, and ‘)’.
“)()((()()”, “()((())))()())”, etc. are examples of bracket sequences.

A range query consists of a starting index and ending index. We wish to find the length of the longest correct bracket sequence within the range specified by the indices (inclusive of both indices).

Understanding Range queries for Bracket Sequences

Let us consider the bracket sequence: ()((())))()()).
And for this sequence, consider the range query: 1 6.
‘1’ is the starting index and ‘6’ is the ending index. Therefore we consider the bracket subsequence: )((()).
The Longest Correct Bracket Subsequence here is (()) and we are required to output its length. Our output is thus: 4.

Implementation

There are various approaches to solving this problem. If one were to use a segment tree, it would have O(log n) time complexity per query. However, we will look at an approach that has O(1) time complexity per query and uses some extra space.

We will be using a stack ‘s’ and two integer arrays ‘open’ and ‘close’. Let us understand their working with an illustration.

First, suppose that the input bracket sequence, ‘arr’ is:

(  )  (  (  (  )  )  )  )  (  )   (  )   )
0  1  2  3  4  5  6  7  8  9  10  11 12  13

The index of each bracket is shown for better understanding.

open and close are integer arrays filled with 0s.

We traverse this bracket sequence from left to right.

With the help of s, we determine the indices of balanced brackets (i.e. those brackets with correct corresponding counterpart).

The use of ‘open’ and ‘close’ in C++

open[i] is made 1, if arr[i] is a balanced open bracket.
Similarly, close[i] is made 1, if arr[i] is a balanced close bracket.

So now open is:

1  0  1  1  1  0  0  0  0  1  0  1  0  0

And close is:

0  1  0  0  0  1  1  1  0  0  1  0  1  0

Our next step is to convert open and close such that open[i] gives us the number of balanced open brackets up to and including the ith position. In the same manner, we transform close so that close[i] gives us the number of balanced close brackets up to and including the ith position.

Accordingly, open is transformed to:

1  1  2  3  4  4  4  4  4  5  5  6  6  6

and close is transformed to:

0  1  1  1  1  2  3  4  4  4  5  5  6  6

How to find the Longest Correct Bracket Subsequence from the range in C++

Let us consider the starting and ending indices to be given by ‘l’ and ‘r’ respectively.

The number of balanced open brackets in this range is open[r – 1] – open[l – 1], if l is not 0. If l is 0, this number is simply open[r – 1].
Note: We do not consider open[r]. This is because an open bracket in the rth position cannot be a part of the longest correct bracket sequence. Similarly, we do not use open[l] but rather
open[l -1] as we do wish to consider a balanced open bracket in the lth position.

The number of balanced close brackets in this range is close[r] – close[l].

The minimum of these values tells us the number of brackets that have a counterpart in the given range. Thus, our output is twice this minimum value.

C++ code

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void create_arrays(char arr[], int open[], int close[]) 
{
  int i;
  stack<int> s;

  // We traverse arr and 
  // change open and close
  // to 1 at appropriate indices

  for (i = 0; i < strlen(arr); i++)
  {
    if (arr[i] == '(') // Push index if ')'
      s.push(i);
    else
    {
      if (!(s.empty())) // Mark 1s in open and close 
                        // to acknowledege balanced ')'
      {
        close[i] = 1;
        open[s.top()] = 1;
        s.pop();
      }
    }
  }
  
  // Now we convert open and 
  // close so as to contain 
  // cumulative values

  for (i = 1; i < strlen(arr); i++)
  {
    open[i] = open[i] + open[i - 1];
    close[i] = close[i] + close[i - 1];
  }
}

void LCBS(int open[], int close[], int l, int r) // This function prints
                                                 // the length of the 
                                                 // Longest Correct 
                                                 // Bracket Sequence
{
  if (r == 0)
  {
    cout << 0;
    return;
  }

  int j = open[r - 1] - (l == 0 ? 0 : open[l - 1]); // j contains the  
                                                    // number of balanced   
                                                    // open brackets in  
                                                    // the specified 
                                                    // range
  int k = close[r] - close[l];                      // k contains the  
                                                    // number of balanced 
                                                    // close brackets in 
                                                    // the specified 
                                                    // range 

  cout << (j < k ? 2 * j : 2 * k) << "\n"; // We output twice the 
                                           // minimum of j and k
}

int main()
{
  char arr[100] = "";
  int open[100] = {}, close[100] = {};
  int l, r;

  cout << "Enter bracket sequence\n";
  cin >> arr;

  create_arrays(arr, open, close);
  
  cout << "Enter Starting Index and Ending Index\n";
  cin >> l >> r;

  LCBS(open, close, l, r);

  return 0;
}

Input

Enter bracket sequence
()((())))()())
Enter Start Index and Ending Index
1 6

Output

Conclusion

In this tutorial, we looked at how to find the length of the Longest Correct Bracket Subsequence for a given range query. We used C++ to implement this in a very efficient manner.