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<bits/stdc++.h> 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<n; i++) { // If opening bracket, push index of it if (str[i] == '(') stk.push(i); else // If closing bracket, i.e.,str[i] = ')' { // If closing bracket, i.e.,str[i] = ')' // && stack is not empty then mark both // "open & close" bracket indexs as 1 . // Pop the previous opening bracket's index if (!stk.empty()) { BCP[i] = 1; BOP[stk.top()] = 1; stk.pop(); } // If stack is empty. else BCP[i] = 0; } } for( int i = 1 ; i < n; i++ ) { BCP[i] += BCP[i-1]; BOP[i] += BOP[i-1]; } } // Function return output of each query in O(1) int query( int BOP[] , int BCP[] , int s , int e ) { if( s != 0 ) return (BCP[e] - (BOP[s-1] - BCP[s-1] ) )*2; else return BCP[e]*2; } // Driver program to test above function int main() { char str[] = "())(())(())("; int n = strlen(str); int BCP[n+1] ={0}; int BOP[n+1] ={0}; constructBlanceArray( BOP , BCP , str, n ); int startIndex = 5, endIndex = 11; cout << "Maximum Length Correct Bracket" " Subsequence between " << startIndex << " and " << endIndex << " = " << query( BOP , BCP, startIndex, endIndex ) << endl; startIndex = 4, endIndex = 5; cout << "Maximum Length Correct Bracket" " Subsequence between " << startIndex << " and " << endIndex << " = " << query( BOP ,BCP, startIndex, endIndex ) << endl; startIndex = 1, endIndex = 5; cout << "Maximum Length Correct Bracket" " Subsequence between " << startIndex << " and " << endIndex << " = " << query( BOP ,BCP, startIndex, endIndex ) << endl; return 0; } |
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).
leave a comment
0 Comments