Tutorialspoint.dev

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<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;
}

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter