Given a string of brackets, the task is to find the number of pairs of brackets involved in a balanced sequence in a given range.
Examples :
Input : ((())(()
Range : 1 5
Range : 3 8
Output : 2
2
Explanation : In range 1 to 5 ((()),
there are the two pairs. In range 3 to 8 ())
((), there are the two pairs.
Input : )()()))
Range : 1 2
Range : 4 7
Output : 0
1
Explanation : In range 1 to 2 )( there
is no pair. In range 4 to 7 ())),
there is the only pair
Prerequisite : Segment Trees
Approach :
Here, in segment tree, for each node, keep some simple elements, like integers or sets or vectors or etc.
For each node keep three integers :
- t = Answer for the interval.
- o = The number of opening brackets ‘(‘ remaining after deleting the brackets those who belong to the correct bracket sequence in this interval with length t.
- c = The number of closing brackets ‘)’ remaining after deleting the brackets those who belong to the correct bracket sequence in this interval with length t.
Now, having these variables, queries can be answered easily using segment tree.
Below is the implementation of the above approach :
C++
// CPP code to find the number of pairs// involved in balanced parentheses#include <bits/stdc++.h>using namespace std;// Our struct nodestruct node { // three variables required int t, o, c;};// Declare array of nodes of very big// size which acts as segment tree here.struct node tree_arr[5 * 1000];// To build a segment tree we pass 1 as// 'id' 0 as 'l' and l as 'n'.// Here, we consider query's interval as [x, y)void build(int id, int l, int r, string s){ /* this base condition is common to build any segment tree*/ // This is the base // Only one element left if (r - l < 2) { // If that element is open bracket if (s[l] == '(') tree_arr[id].o = 1; // If that element is open bracket else tree_arr[id].c = 1; return; } // Next three lines are common // for any segment tree. int mid = (l + r) / 2; // for left tree build(2 * id, l, mid, s); // for right tree build(2 * id + 1, mid, r, s); // Here we take minimum of left tree // opening brackets and right tree // closing brackets int tmp = min(tree_arr[2 * id].o, tree_arr[2 * id + 1].c); // we add that to our answer. tree_arr[id].t = tree_arr[2 * id].t + tree_arr[2 * id + 1].t + tmp; // Remove the answer from opening brackets tree_arr[id].o = tree_arr[2 * id].o + tree_arr[2 * id + 1].o - tmp; // Remove the answer from opening brackets tree_arr[id].c = tree_arr[2 * id].c + tree_arr[2 * id + 1].c - tmp;}// This will return the answer for each query.// Here we consider query's interval as [x, y)node segment(int x, int y, int id, int l, int r, string s){ // If the given interval is out of range if (l >= y || x >= r) { struct node tem; tem.t = 0; tem.o = 0; tem.c = 0; return tem; } // If the given interval completely lies if (x <= l && r <= y) return tree_arr[id]; // Next three lines are common for // any segment tree. int mid = (l + r) / 2; // For left tree struct node a = segment(x, y, 2 * id, l, mid, s); // For right tree struct node b = segment(x, y, 2 * id + 1, mid, r, s); // Same as made in build function int temp; temp = min(a.o, b.c); struct node vis; vis.t = a.t + b.t + temp; vis.o = a.o + b.o - temp; vis.c = a.c + b.c - temp; return vis;}// Driver codeint main(){ string s = "((())(()"; int n = s.size(); // range for query int a = 3, b = 8; build(1, 0, n, s); // Here we consider query's interval as [a, b) // We subtract 1 from 'a' because indexes start // from 0. struct node p = segment(a-1, b, 1, 0, n, s); cout << p.t << endl; return 0;} |
Java
// Java code for the above approachimport java.util.Scanner;// Our struct nodeclass Node { int t, o, c;}class SegmentTree { Node[] tree_arr; // Declare array of nodes of very big size which acts as segment tree here. SegmentTree(int n) { tree_arr = new Node[5 * n]; for (int i = 0; i < 5 * n; i++) { tree_arr[i] = new Node(); } } // To build a segment tree we pass 1 as 'id' 0 as 'l' and l as 'n'. // Here, we consider query's interval as [x, y) void build(int id, int l, int r, String s) { /* this base condition is common to build any segment tree*/ // This is the base // Only one element left if (r - l < 2) { // If that element is open bracket if (s.charAt(l) == '(') { tree_arr[id].o = 1; } else { tree_arr[id].c = 1; } return; } // Next three lines are common // for any segment tree. int mid = (l + r) / 2; // for left tree build(2 * id, l, mid, s); // for right tree build(2 * id + 1, mid, r, s); // Here we take minimum of left tree opening brackets and right tree closing brackets int temp = Math.min(tree_arr[2 * id].o, tree_arr[2 * id + 1].c); // we add that to our answer. tree_arr[id].t = tree_arr[2 * id].t + tree_arr[2 * id + 1].t + temp; // Remove the answer from opening brackets tree_arr[id].o = tree_arr[2 * id].o + tree_arr[2 * id + 1].o - temp; // Remove the answer from opening brackets tree_arr[id].c = tree_arr[2 * id].c + tree_arr[2 * id + 1].c - temp; } // This will return the answer for each query. // Here we consider query's interval as [x, y) Node segment(int x, int y, int id, int l, int r, String s) { // If the given interval is out of range if (l >= y || x >= r) { Node temp = new Node(); temp.t = 0; temp.o = 0; temp.c = 0; return temp; } // If the given interval completely lies if (x <= l && r <= y) { return tree_arr[id]; } // Next three lines are common for // any segment tree. int mid = (l + r) / 2; // For left tree Node a = segment(x, y, 2 * id, l, mid, s); // For right tree Node b = segment(x, y, 2 * id + 1, mid, r, s); int temp = Math.min(a.o, b.c); Node res = new Node(); res.t = a.t + b.t + temp; res.o = a.o + b.o - temp; res.c = a.c + b.c - temp; return res; } // Driver code public static void main(String[] args) { String s = "((())(()"; int n = s.length(); SegmentTree obj = new SegmentTree(n); obj.build(1, 0, n, s); int a = 3, b = 8; Node p = obj.segment(a - 1, b, 1, 0, n, s); System.out.println(p.t); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 code to find the number of pairs# involved in balanced parentheses# Our struct nodeclass node : def __init__(self): # three variables required self.t = 0 self.o = 0 self.c = 0# Declare array of nodes of very big# size which acts as segment tree here.tree_arr = [node()]*(5 * 1000)# To build asegmenttree we pass 1 as# 'id' 0 as 'l' and l as 'n'.# Here, we consider query's interval as [x, y)def build(id, l, r, s): global tree_arr tree_arr[id] = node() # this base condition is common to # build any segment tree # This is the base # Only one element left if (r - l < 2) : # If that element is open bracket if (s[l] == "("): tree_arr[id].o = 1 # If that element is open bracket else: tree_arr[id].c = 1 return # Next three lines are common # for any segment tree. mid = int( (l + r) / 2) # for left tree build(2 * id, l, mid, s) # for right tree build(2 * id + 1, mid, r, s) # Here we take minimum of left tree # opening brackets and right tree # closing brackets tmp = min(tree_arr[2 * id].o, tree_arr[2 * id + 1].c) # we add that to our answer. tree_arr[id].t = tree_arr[2 * id].t + \ tree_arr[2 * id + 1].t + tmp # Remove the answer from opening brackets tree_arr[id].o = tree_arr[2 * id].o + \ tree_arr[2 * id + 1].o - tmp # Remove the answer from opening brackets tree_arr[id].c = tree_arr[2 * id].c + \ tree_arr[2 * id + 1].c - tmp# This will return the answer for each query.# Here we consider query's interval as [x, y)def segment(x, y, id, l, r, s): global tree_arr # If the given interval is out of range if (l >= y or x >= r) : tem= node() tem.t = 0 tem.o = 0 tem.c = 0 return tem # If the given interval completely lies if (x <= l and r <= y): return tree_arr[id] # Next three lines are common for # any segment tree. mid = int((l + r) / 2) # For left tree a = segment(x, y, 2 * id, l, mid, s) # For right tree b = segment(x, y, 2 * id + 1, mid, r, s) # Same as made in build function temp= 0 temp = min(a.o, b.c) vis = node() vis.t = a.t + b.t + temp vis.o = a.o + b.o - temp vis.c = a.c + b.c - temp return vis# Driver codes = "((())(()"n = len(s)# range for querya = 3b = 8 build(1, 0, n, s) # Here we consider query's interval as [a, b)# We subtract 1 from 'a' because indexes start# from 0.p = segment(a-1, b, 1, 0, n, s)print(p.t )# This code is contributed by Arnab Kundu |
C#
using System;class SegmentTree { public Node[] tree_arr; // Our struct node public struct Node { public int t, o, c; } // Declare array of nodes of very big size which acts as // segment tree here. public SegmentTree(int n) { tree_arr = new Node[5 * n]; for (int i = 0; i < 5 * n; i++) { tree_arr[i] = new Node(); } } // To build a segment tree we pass 1 as 'id' 0 as 'l' // and l as 'n'. Here, we consider query's interval as // [x, y) public void build(int id, int l, int r, string s) { /* this base condition is common to build any segment tree*/ // This is the base // Only one element left if (r - l < 2) { // If that element is open bracket if (s[l] == '(') { tree_arr[id].o = 1; } else { tree_arr[id].c = 1; } return; } // Next three lines are common // for any segment tree. int mid = (l + r) / 2; // for left tree build(2 * id, l, mid, s); // for right tree build(2 * id + 1, mid, r, s); // Here we take minimum of left tree opening // brackets and right tree closing brackets int temp = Math.Min(tree_arr[2 * id].o, tree_arr[2 * id + 1].c); // we add that to our answer. tree_arr[id].t = tree_arr[2 * id].t + tree_arr[2 * id + 1].t + temp; // Remove the answer from opening brackets tree_arr[id].o = tree_arr[2 * id].o + tree_arr[2 * id + 1].o - temp; // Remove the answer from opening brackets tree_arr[id].c = tree_arr[2 * id].c + tree_arr[2 * id + 1].c - temp; } // This will return the answer for each query. // Here we consider query's interval as [x, y) public Node segment(int x, int y, int id, int l, int r, string s) { // If the given interval is out of range if (l >= y || x >= r) { Node temp = new Node(); temp.t = 0; temp.o = 0; temp.c = 0; return temp; } // If the given interval completely lies if (x <= l && r <= y) { return tree_arr[id]; } // Next three lines are common for // any segment tree. int mid = (l + r) / 2; // For left tree Node a = segment(x, y, 2 * id, l, mid, s); // For right tree Node b = segment(x, y, 2 * id + 1, mid, r, s); int te = Math.Min(a.o, b.c); Node res = new Node(); res.t = a.t + b.t + te; res.o = a.o + b.o - te; res.c = a.c + b.c - te; return res; } // Driver code public static void Main(string[] args) { string s = "((())(()"; int n = s.Length; SegmentTree obj = new SegmentTree(n); obj.build(1, 0, n, s); int a = 3, b = 8; Node p = obj.segment(a - 1, b, 1, 0, n, s); Console.WriteLine(p.t); }} |
Javascript
// Our struct nodefunction node() { // three variables required this.t = 0; this.o = 0; this.c = 0;}// Declare array of nodes of very big// size which acts as segment tree here.let tree_arr = new Array(5 * 1000);// To build a segment tree we pass 1 as// 'id' 0 as 'l' and l as 'n'.// Here, we consider query's interval as [x, y)function build(id, l, r, s){ /* this base condition is common to build any segment tree*/ // This is the base // Only one element left if (r - l < 2) { // If that element is open bracket if (s[l] == '(') tree_arr[id].o = 1; // If that element is open bracket else tree_arr[id].c = 1; return; } // Next three lines are common // for any segment tree. let mid = Math.floor((l + r) / 2); // for left tree build(2 * id, l, mid, s); // for right tree build(2 * id + 1, mid, r, s); // Here we take minimum of left tree // opening brackets and right tree // closing brackets let tmp = Math.min(tree_arr[2 * id].o, tree_arr[2 * id + 1].c); // we add that to our answer. tree_arr[id].t = tree_arr[2 * id].t + tree_arr[2 * id + 1].t + tmp; // Remove the answer from opening brackets tree_arr[id].o = tree_arr[2 * id].o + tree_arr[2 * id + 1].o - tmp; // Remove the answer from opening brackets tree_arr[id].c = tree_arr[2 * id].c + tree_arr[2 * id + 1].c - tmp;}// This will return the answer for each query.// Here we consider query's interval as [x, y)function segment(x, y, id, l, r, s){ // If the given interval is out of range if (l >= y || x >= r) { let tem = new node(); return tem; } // If the given interval completely lies if (x <= l && r <= y) return tree_arr[id]; // Next three lines are common for // any segment tree. let mid = Math.floor((l + r) / 2); // For left tree let a = segment(x, y, 2 * id, l, mid, s); // For right tree let b = segment(x, y, 2 * id + 1, mid, r, s); // Same as made in build function let temp; temp = Math.min(a.o, b.c); let vis = new node(); vis.t = a.t + b.t + temp; vis.o = a.o + b.o - temp; vis.c = a.c + b.c - temp; return vis;}// Driver codefunction main(){ let s = "((())(()"; let n = s.length; // range for query let a = 3, b = 8; build(1, 0, n, s); // Here we consider query's interval as [a, b) // We subtract 1 from 'a' because indexes start // from 0. let p = segment(a-1, b, 1, 0, n, s); console.log(p.t); return 0;}main(); |
Output
2
Time Complexity: O(N), where N is the length of the string.
Auxiliary Space: O(N), for storing the segment tree.
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!
