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 precomputationvoid 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 functionint 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 timeimport java.util.*;class GFG{/*BOP[] stands for "Balanced open parentheses" BCP[] stands for "Balanced close parentheses"*/// Function for precomputationstatic 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 codepublic 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 precomputationdef 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 codeif __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 timeusing 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 precomputationfunction 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 functionvar 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
