Range Queries for Longest Correct Bracket Subsequence Set | 2

Last Updated : 07 Nov, 2022

Given a bracket sequence or in other words a string S of length n, consisting of characters ‘(‘ and ‘)’. Find the length of the maximum correct bracket subsequence of sequence for a given query range. Note: A correct bracket sequence is the one that has 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 go to see a solution that works in O(1) for each query.

The idea is based on the Post length of the longest valid balanced substring If we marked indexes of all Balanced parentheses/brackets 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 balance bracket.
Traverse 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 indexes as 1.
BCP[i] = 1; 
BOP[stk.top()] = 1;

And At last, 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]])*2;

Below is the implementation of the above idea.

C++

// 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 constructBalanceArray(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 indexes 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 (BOP[s - 1] == BOP[s]) {
        return (BCP[e] - BOP[s]) * 2;
    }
 
    else {
        return (BCP[e] - BOP[s] + 1) * 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 };
 
    constructBalanceArray(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;
}

Java

// Java code to answer the query in constant time
import java.util.*;
 
class GFG{
 
/*
BOP[] stands for "Balanced open parentheses" 
BCP[] stands for "Balanced close parentheses"
 
*/
 
// Function for precomputation
static void constructBalanceArray(int BOP[], int BCP[],
                                String str, int n)
{
     
    // Create a stack and push -1
    // as initial index to it.
    Stack<Integer> stk = new Stack<>();;
 
    // Traverse all characters of given String
    for(int i = 0; i < n; i++) 
    {
         
        // If opening bracket, push index of it
        if (str.charAt(i) == '(')
            stk.add(i);
             
        // If closing bracket, i.e., str[i] = ')'
        else
        {
             
            // If closing bracket, i.e., str[i] = ')'
            // && stack is not empty then mark both
            // "open & close" bracket indexes as 1 .
            // Pop the previous opening bracket's index
            if (!stk.isEmpty())
            {
                BCP[i] = 1;
                BOP[stk.peek()] = 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)
static int query(int BOP[], int BCP[],
                 int s, int e)
{
    if (BOP[s - 1] == BOP[s])
    {
        return (BCP[e] - BOP[s]) * 2;
    }
    else
    {
        return (BCP[e] - BOP[s] + 1) * 2;
    }
}
 
// Driver code
public static void main(String[] args)
{
 
    String str = "())(())(())(";
    int n = str.length();
 
    int BCP[] = new int[n + 1];
    int BOP[] = new int[n + 1];
 
    constructBalanceArray(BOP, BCP, str, n);
 
    int startIndex = 5, endIndex = 11;
    System.out.print("Maximum Length Correct " + 
                     "Bracket Subsequence between " + 
                     startIndex + " and " + endIndex +
                     " = " + query(BOP, BCP, startIndex,
                                   endIndex) + "\n");
 
    startIndex = 4;
    endIndex = 5;
    System.out.print("Maximum Length Correct " +  
                     "Bracket Subsequence between " + 
                     startIndex + " and " + endIndex +
                     " = " + query(BOP, BCP, startIndex,
                                   endIndex) + "\n");
 
    startIndex = 1;
    endIndex = 5;
    System.out.print("Maximum Length Correct " +
                     "Bracket Subsequence between " +
                     startIndex + " and " + endIndex +
                     " = " + query(BOP, BCP, startIndex,
                                   endIndex) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 code to answer the query in constant time
 
'''
BOP[] stands for "Balanced open parentheses" 
BCP[] stands for "Balanced close parentheses"
 
'''
# Function for precomputation
def constructBalanceArray(BOP, BCP, str, n):
     
    # Create a stack and push -1
    # as initial index to it.
    stk = []
 
    # Traverse all characters of given String
    for i in range(n):
         
        # If opening bracket, push index of it
        if (str[i] == '('):
            stk.append(i);
             
        # If closing bracket, i.e., str[i] = ')'
        else:
             
            # If closing bracket, i.e., str[i] = ')'
            # && stack is not empty then mark both
            # "open & close" bracket indexes as 1 .
            # Pop the previous opening bracket's index
            if (len(stk) != 0):
                BCP[i] = 1;
                BOP[stk[-1]] = 1;
                stk.pop();
 
            # If stack is empty.
            else:
                BCP[i] = 0;
         
    for i in range(1, n):
 
        BCP[i] += BCP[i - 1];
        BOP[i] += BOP[i - 1];
     
# Function return output of each query in O(1)
def query(BOP, BCP, s, e):
 
    if (BOP[s - 1] == BOP[s]):
        return (BCP[e] - BOP[s]) * 2;
     
    else:
        return (BCP[e] - BOP[s] + 1) * 2;
 
# Driver code
if __name__=='__main__':
 
    string = "())(())(())(";
    n = len(string)
 
    BCP = [0 for i in range(n + 1)];
    BOP = [0 for i in range(n + 1)];
 
    constructBalanceArray(BOP, BCP, string, n);
    startIndex = 5
    endIndex = 11;
    print("Maximum Length Correct " +
                     "Bracket Subsequence between " +
                     str(startIndex) + " and " + str(endIndex) +
                     " = " + str(query(BOP, BCP, startIndex,
                                   endIndex)));
    startIndex = 4;
    endIndex = 5;
    print("Maximum Length Correct " + 
                     "Bracket Subsequence between " +
                     str(startIndex) + " and " + str(endIndex) +
                     " = " + str(query(BOP, BCP, startIndex,
                                   endIndex)))
    startIndex = 1;
    endIndex = 5;
    print("Maximum Length Correct " +
                     "Bracket Subsequence between " +
                     str(startIndex) + " and " + str(endIndex) +
                     " = " + str(query(BOP, BCP, startIndex,
                                   endIndex)));
 
# This code is contributed by rutvik_56.

C#

// C# code to answer the query
// in constant time
using System;
using System.Collections.Generic;
class GFG{
 
    /*
    BOP[] stands for "Balanced open parentheses"
    BCP[] stands for "Balanced close parentheses"
    */
 
    // Function for precomputation
    static void constructBalanceArray(int[] BOP, int[] BCP,
                                     String str, int n)
    {
 
        // Create a stack and push -1
        // as initial index to it.
        Stack<int> stk = new Stack<int>();;
 
        // 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);
 
            // If closing bracket, i.e., str[i] = ')'
            else
            {
 
                // If closing bracket, i.e., str[i] = ')'
                // && stack is not empty then mark both
                // "open & close" bracket indexes as 1 .
                // Pop the previous opening bracket's index
                if (stk.Count != 0) 
                {
                    BCP[i] = 1;
                    BOP[stk.Peek()] = 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)
    static int query(int[] BOP, int[] BCP, int s, int e)
    {
        if (BOP[s - 1] == BOP[s]) 
        {
            return (BCP[e] - BOP[s]) * 2;
        }
        else
        {
            return (BCP[e] - BOP[s] + 1) * 2;
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String str = "())(())(())(";
        int n = str.Length;
        int[] BCP = new int[n + 1];
        int[] BOP = new int[n + 1];
        constructBalanceArray(BOP, BCP, str, n);
        int startIndex = 5, endIndex = 11;
        Console.Write("Maximum Length Correct " + 
                      "Bracket Subsequence between " + 
                       startIndex + " and " + endIndex + " = " + 
                       query(BOP, BCP, startIndex, endIndex) + "\n");
 
        startIndex = 4;
        endIndex = 5;
        Console.Write("Maximum Length Correct " + 
                      "Bracket Subsequence between " + 
                       startIndex + " and " + endIndex + " = " +
                       query(BOP, BCP, startIndex, endIndex) + "\n");
 
        startIndex = 1;
        endIndex = 5;
        Console.Write("Maximum Length Correct " + 
                      "Bracket Subsequence between " + 
                       startIndex + " and " + endIndex + " = " + 
                       query(BOP, BCP, startIndex, endIndex) + "\n");
    }
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript code to answer the query in constant time
 
/*
BOP[] stands for "Balanced open parentheses" 
BCP[] stands for "Balanced close parentheses"
 
*/
 
// function for precomputation
function constructBalanceArray(BOP, BCP, str, n)
{
 
    // Create a stack and push -1 as initial index to it.
    var stk = [];
 
    // Initialize result
    var result = 0;
 
    // Traverse all characters of given string
    for (var 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 indexes as 1 .
            // Pop the previous opening bracket's index
            if (stk.length!=0) {
                BCP[i] = 1;
                BOP[stk[stk.length-1]] = 1;
                stk.pop();
            }
 
            // If stack is empty.
            else
                BCP[i] = 0;
        }
    }
 
    for (var i = 1; i < n; i++) {
        BCP[i] += BCP[i - 1];
        BOP[i] += BOP[i - 1];
    }
}
 
// Function return output of each query in O(1)
function query(BOP, BCP, s, e)
{
    if (BOP[s - 1] == BOP[s]) {
        return (BCP[e] - BOP[s]) * 2;
    }
 
    else {
        return (BCP[e] - BOP[s] + 1) * 2;
    }
}
 
// Driver program to test above function
var str = "())(())(())(";
var n = str.length;
var BCP = Array(n+1).fill(0);
var BOP = Array(n+1).fill(0);
constructBalanceArray(BOP, BCP, str, n);
var startIndex = 5, endIndex = 11;
 
document.write( "Maximum Length Correct Bracket"+
        " Subsequence between "
     + startIndex + " and " + endIndex + " = "
     + query(BOP, BCP, startIndex, endIndex) + "<br>");;
startIndex = 4, endIndex = 5;
 
document.write( "Maximum Length Correct Bracket"+
        " Subsequence between "
     + startIndex + " and " + endIndex + " = "
     + query(BOP, BCP, startIndex, endIndex) + "<br>");;
startIndex = 1, endIndex = 5;
 
document.write( "Maximum Length Correct Bracket"+
        " Subsequence between "
     + startIndex + " and " + endIndex + " = "
     + query(BOP, BCP, startIndex, endIndex) + "<br>");;
 
 
</script>

Output

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

The time complexity for each query is O(1).
Overall time Complexity: O(n)
Auxiliary Space: O(n)

Suggest improvement

Remove brackets from an algebraic string containing + and - operators

Share your thoughts in the comments

Stack implementation in different language

Some questions related to Stack implementation

Easy problems on Stack

Intermediate problems on Stack

Hard problems on Stack