# Range Queries for Longest Correct Bracket Subsequence Set | 2

Given a bracket sequence or in other words a string S of length n, consisting of characters ‘(‘ and ‘)’. Find length of the maximum correct bracket subsequence of sequence for a given query range. Note: A correct bracket sequence is the one that have matched bracket pairs or which contains another nested correct bracket sequence. For e.g (), (()), ()() are some correct bracket sequence.

Examples:

```Input : S = ())(())(())(
Start Index of Range = 0,
End Index of Range = 11
Output : 10
Explanation:  Longest Correct Bracket Subsequence is ()(())(())

Input : S = ())(())(())(
Start Index of Range = 1,
End Index of Range = 2
Output : 0
```

Approach : In the Previous post (SET 1) we discussed a solution that works in O(long) for each query, now is this post we will going to see a solution that works in O(1) for each query.
Idea is based on the Post length of the longest valid balanced substring If we marked indexes of all Balanced parentheses/bracket in a temporary array (here we named it BCP[], BOP[] ) then we answer each query in O(1) time.
Algorithm :

```stack is used to get the index of blanace Breacket
Travese a string from 0 ..to n
IF we seen a closing bracket,
( i.e., str[i] = ')' && stack is not empty )

Then mark both "open & close" bracket indexs as 1 .
BCP[i] = 1;
BOP[stk.top()] = 1;

And At lest stored cumulative sum of BCP[] & BOP[]
Run a loop from 1 to n
BOP[i] +=BOP[i-1], BCP[i] +=BCP[i-1]
```

Now you can answer each query in O(1) time

```(BCP[e] - (BOP[s-1] - BCP[s-1] ) )*2;
```

Below is the implementation of above idea.

 `// CPP code to answer the query in constant time ` `#include ` `using` `namespace` `std; ` ` `  `/* ` `BOP[] stands for "Balanced open parentheses"  ` `BCP[] stands for "Balanced close parentheses" ` ` `  `*/` ` `  `// function for precomputation  ` `void` `constructBlanceArray( ``int` `BOP[] , ``int` `BCP[] ,  ` `                           ``char``* str , ``int` `n ) ` `{ ` ` `  `    ``// Create a stack and push -1 as initial index to it. ` `    ``stack<``int``> stk; ` ` `  `    ``// Initialize result ` `    ``int` `result = 0; ` ` `  `    ``// Traverse all characters of given string ` `    ``for` `(``int` `i=0; i

Output:

```Maximum Length Correct Bracket Subsequence between 5 and 11 = 6
Maximum Length Correct Bracket Subsequence between 4 and 5 = 2
Maximum Length Correct Bracket Subsequence between 1 and 5 = 2
```

Time complexity for each query is O(1).