Open In App

Range Queries for Longest Correct Bracket Subsequence Set | 2

Last Updated : 30 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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++ 
#include <bits/stdc++.h>
using namespace std;

void constructBalanceArray(int BOP[], int BCP[], const char* str, int n) {
    stack<int> stk;
    fill(BOP, BOP + n + 1, 0);
    fill(BCP, BCP + n + 1, 0);

    for (int i = 0; i < n; i++) {
        if (str[i] == '(') {
            stk.push(i);
        } else { // It's a ')'
            if (!stk.empty()) {
                int openIndex = stk.top();
                stk.pop();
                BOP[openIndex] = 1; // There's a valid '(' at openIndex
                BCP[i] = 1;         // There's a valid ')' at i
            }
        }
    }

    // Convert the BOP and BCP into prefix sums
    for (int i = 1; i <= n; i++) {
        BOP[i] += BOP[i - 1];
        BCP[i] += BCP[i - 1];
    }
}

int query(int BOP[], int BCP[], int s, int e) {
    if (s == 0) {
        return (BCP[e] - BOP[s]) * 2;
    } else {
        return (BCP[e] - BCP[s - 1] - (BOP[s] - BOP[s - 1])) * 2;
    }
}

int main() {
    const char str[] = "())(())(())(";
    int n = strlen(str);

    int BCP[n + 1], BOP[n + 1];

    constructBalanceArray(BOP, BCP, str, n);

    vector<pair<int, int>> queries = {{4, 11}, {3, 4}, {0, 2}, {0, 4}, {1, 2}};
    for (const auto& query_pair : queries) {
        int start = query_pair.first;
        int end = query_pair.second;
        cout << "Maximum Length Correct Bracket Subsequence between " << start + 1 << " and " << end + 1 << " = " << query(BOP, BCP, start, end) << endl;
    }

    return 0;
}
Java 
import java.util.*;

class GFG {

    static void constructBalanceArray(int[] BOP, int[] BCP, String str, int n) {
        Stack<Integer> stk = new Stack<>();
        Arrays.fill(BOP, 0);
        Arrays.fill(BCP, 0);

        for (int i = 0; i < n; i++) {
            if (str.charAt(i) == '(') {
                stk.push(i);
            } else { // It's a ')'
                if (!stk.isEmpty()) {
                    int openIndex = stk.pop();
                    BOP[openIndex] = 1; // Mark this '(' as balanced
                    BCP[i] = 1;         // Mark this ')' as balanced
                }
            }
        }

        // Convert to prefix sums
        for (int i = 1; i < n; i++) {
            BOP[i] += BOP[i - 1];
            BCP[i] += BCP[i - 1];
        }
    }

    static int query(int[] BOP, int[] BCP, int s, int e) {
        if (s > 0 && BOP[s - 1] == BOP[s]) {
            return (BCP[e] - BOP[s]) * 2;
        } else {
            return (BCP[e] - (s > 0 ? BOP[s - 1] : 0)) * 2;
        }
    }

    public static void main(String[] args) {
        String str = "())(())(())(";
        int n = str.length();
        int[] BCP = new int[n];
        int[] BOP = new int[n];

        constructBalanceArray(BOP, BCP, str, n);

        // Define the queries
        int[][] queries = {
            {5, 11}, // indices are 0-based, add 1 if 1-based is needed
            {4, 5},
            {1, 5},
            {0, 2}
        };

        for (int[] query : queries) {
            int startIndex = query[0];
            int endIndex = query[1];
            System.out.println("Maximum Length Correct Bracket Subsequence between " +
                               (startIndex + 1) + " and " + (endIndex + 1) +
                               " = " + query(BOP, BCP, startIndex, endIndex));
        }
    }
}
Python3 
def constructBalanceArray(BOP, BCP, s, n):
    stk = []  # No need to push -1 as mentioned in the comment; we never use that

    for i in range(n):
        if s[i] == '(':
            stk.append(i)
        else:
            if stk:
                open_index = stk.pop()
                BOP[open_index] = 1
                BCP[i] = 1
            # No else needed here; the initial values are zero

    # Convert to prefix sums
    for i in range(1, n):
        BOP[i] += BOP[i - 1]
        BCP[i] += BCP[i - 1]

def query(BOP, BCP, s, e):
    s_adjusted = s - 1  # Adjusting for 0-based index access
    e_adjusted = e

    if s_adjusted > 0 and BOP[s_adjusted - 1] == BOP[s_adjusted]:
        return (BCP[e_adjusted] - BOP[s_adjusted]) * 2
    else:
        return (BCP[e_adjusted] - (BOP[s_adjusted - 1] if s_adjusted > 0 else 0)) * 2

if __name__ == '__main__':
    string = "())(())(())("
    n = len(string)

    BCP = [0] * n
    BOP = [0] * n

    constructBalanceArray(BOP, BCP, string, n)

    queries = [(5, 11), (4, 5), (1, 5)]
    for start, end in queries:
        max_length = query(BOP, BCP, start, end)
        print(f"Maximum Length of Balanced Bracket Subsequence from {start} to {end} = {max_length}")
C# 
using System;
using System.Collections.Generic;

class GFG
{
    // Function for precomputation
    static void constructBalanceArray(int[] BOP, int[] BCP, string str, int n)
    {
        Stack<int> stk = new Stack<int>();

        for (int i = 0; i < n; i++)
        {
            if (str[i] == '(')
            {
                stk.Push(i);
            }
            else
            {
                if (stk.Count > 0)
                {
                    int matchedOpenIndex = stk.Pop();
                    BOP[matchedOpenIndex] = 1;
                    BCP[i] = 1;
                }
            }
        }

        // Building prefix sums
        for (int i = 1; i < n; i++)
        {
            BOP[i] += BOP[i - 1];
            BCP[i] += BCP[i - 1];
        }
    }

    // Function to return output of each query in O(1)
    static int query(int[] BOP, int[] BCP, int s, int e)
    {
        if (s > 1 && BOP[s - 2] == BOP[s - 1])
        {
            return (BCP[e] - BOP[s - 1]) * 2;
        }
        else
        {
            return (BCP[e] - (s > 1 ? BOP[s - 2] : 0)) * 2;
        }
    }

    // Driver code
    public static void Main()
    {
        string str = "())(())(())(";
        int n = str.Length;
        int[] BCP = new int[n + 1];
        int[] BOP = new int[n + 1];
        constructBalanceArray(BOP, BCP, str, n);

        // Test cases
        var queries = new[] { (5, 11), (4, 5), (1, 5) };
        foreach (var (startIndex, endIndex) in queries)
        {
            int maxLen = query(BOP, BCP, startIndex, endIndex);
            Console.WriteLine($"Maximum Length Correct Bracket Subsequence between {startIndex} and {endIndex} = {maxLen}");
        }
    }
}
Javascript 
<script>
// Function for precomputation
function constructBalanceArray(BOP, BCP, str, n) {
    var stk = [];
    for (var i = 0; i < n; i++) {
        if (str[i] === '(')
            stk.push(i);
        else {
            if (stk.length !== 0) {
                BCP[i] = 1;
                BOP[stk[stk.length - 1]] = 1;
                stk.pop();
            } else
                BCP[i] = 0;
        }
    }

    for (var i = 1; i < n; i++) {
        BCP[i] += BCP[i - 1];
        BOP[i] += BOP[i - 1];
    }
}

// Function to 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 of Correct Bracket Subsequence between " +
    startIndex + " and " + endIndex + " = " +
    query(BOP, BCP, startIndex, endIndex) + "<br>");

startIndex = 4, endIndex = 5;
document.write("Maximum Length of Correct Bracket Subsequence between " +
    startIndex + " and " + endIndex + " = " +
    query(BOP, BCP, startIndex, endIndex) + "<br>");

startIndex = 1, endIndex = 5;
document.write("Maximum Length of 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)



N
Nishant_Singh
Improve
Previous Article
Remove brackets from an algebraic string containing + and - operators

Similar Reads

Range Queries for Longest Correct Bracket Subsequence
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 (), (())
15+ min read
Check if the bracket sequence can be balanced with at most one change in the position of a bracket | Set 2
Given a bracket sequence as a string str, the task is to find whether the given string can be balanced by moving at most one bracket from its original place in the sequence to any other position.Examples: Input: str = ")(()" Output: Yes As by moving s[0] to the end will make it valid. "(())"Input: str = "()))(()" Output: No Approach: The problem ca
5 min read
Check if the bracket sequence can be balanced with at most one change in the position of a bracket
Given an unbalanced bracket sequence as a string str, the task is to find whether the given string can be balanced by moving at most one bracket from its original place in the sequence to any other position.Examples: Input: str = ")(()" Output: Yes As by moving s[0] to the end will make it valid. "(())"Input: str = "()))(()" Output: No Approach: Co
6 min read
Maximum Pairs of Bracket Sequences which can be concatenated to form a Regular Bracket Sequence
Given an array arr[] of N strings such that each string consists of characters '(' and ')', the task is to find the maximum number of pairs of strings such that the concatenation of the two strings is a Regular Bracket Sequence. A Regular Bracket Sequence is a string consisting of brackets '(' and ')' such that every prefix from the beginning of th
9 min read
Find index of closing bracket for a given opening bracket in an expression
Given a string with brackets. If the start index of the open bracket is given, find the index of the closing bracket. Examples: Input : string = [ABC[23]][89] index = 0 Output : 8 The opening bracket at index 0 corresponds to closing bracket at index 8.Recommended PracticeClosing bracket indexTry It! The idea is to use Stack data structure. We trav
7 min read
RGYB(color) Slots Game to guess the correct color for the correct slot
Given that you have four slots, and each slot will contain a color red (R), yellow (Y), green (G), blue (B) respectively. For example, if you select YGGR (Slot-1 is yellow, Slots-2 and -3 are green, Slot -4 is red). The colors of slots are not known to you beforehand. You will make a guess about the colors. You might, for example, guess YRGB. When
9 min read
Longest Increasing Subsequence using Longest Common Subsequence Algorithm
Given an array arr[] of N integers, the task is to find and print the Longest Increasing Subsequence.Examples: Input: arr[] = {12, 34, 1, 5, 40, 80} Output: 4 {12, 34, 40, 80} and {1, 5, 40, 80} are the longest increasing subsequences.Input: arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80} Output: 6 Prerequisite: LCS, LISApproach: The longest increasing
12 min read
Array range queries over range queries
Given an array of size n and a give set of commands of size m. The commands are enumerated from 1 to m. These commands can be of the following two types of commands: Type 1 [l r (1 &lt;= l &lt;= r &lt;= n)] : Increase all elements of the array by one, whose indices belongs to the range [l, r]. In these queries of the index is inclusive in the range
15+ min read
Number of balanced bracket subsequence of length 2 and 4
Given a bracket sequence of even length. The task is to find how many ways are there to make balanced bracket subsequences from the given sequence of length 2 and 4. The sequence () is a bracket sequence of length 2. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of t
9 min read
Longest Subsequence with absolute difference of pairs as at least Subsequence's maximum
Given an array arr[] of length N. The task is to find the length of the longest subsequence of the array such that the absolute difference between any pair of elements is greater than or equal to the maximum element in that subsequence. Examples: Input: N = 6, arr[] = {1, 1, 0, 0, 0, 0}Output: 4Explanation: Considering 0 as max element of subsequen
7 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox