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.
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.
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.
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).