Given an array arr[] consisting of N strings where each string consists of ‘(‘ and ‘)’, the task is to check if a Regular Bracket Sequence can be formed with the concatenation of the given strings or not. If found to be true, then print Yes. Otherwise print No.
Examples:
Input: arr[] = { “)”, “()(” }
Output: Yes
Explanation: The valid string is S[1] + S[0] = “()()”.Input: arr[] = { “)(“, “()”}
Output: No
Explanation: No valid Regular bracket sequences are possible.
Approach: The given problem can be solved with the help of the Greedy Approach which is based on the following observations:
- If a string contains a consecutive pair of letters ’(’ and ’)’, then removing those two letters does not affect the result.
- By repeating this operation, each S[i] becomes a (possibly empty) string consisting of 0 or more repetition of ’)’, followed by 0 or more repetition of ’(’.
- Then every string can be denoted with two variables A[i] = the number of ’)’, and B[i] = the number of ’(’.
- Maintain a pair vector v[][] to store these values.
- Now, separate there two strings into two separate vectors pos[] and neg[].
- pos[] will store those strings in which the total sum is positive and neg[] with store strings whose total sum is negative.
- Now the optimal way is to concatenate positive strings first then negative strings after that in their increasing order.
Follow the steps below to solve the problem:
- Maintain a pair vector v[][] that will store the values {sum, minimum prefix}, where the sum is calculated by +1 for ‘(‘ and -1 for ‘)’ and the minimum prefix is the maximum consecutive ‘)’ in the string.
- Iterate over the range [0. N) using the variable i and perform the following steps:
- Initialize 2 variables sum and pre as 0 to store the sum and minimum prefix for the given string.
- Iterate over the range [0, M) for every character of the string, and if the current character is ‘(‘ then increment sum by 1 else decrease it by 1 and set the value of pre as the minimum of pre or sum at every step.
- Set the value of v[I] as { sum, pre }.
- Iterate over the range [0. N) for elements in v[] and for each pair if the sum is positive then store the value {-min_prefix, sum} in pos[] vector otherwise {sum – min_prefix, -sum} in neg[] vector.
- Sort these vectors in increasing order.
- Initialize the variable open as 0.
- Iterate over the range [0. size) where size is the size of the vector pos[] using the iterator variable p and if open – p.first is greater than equal to 0 then add p.second to the variable open. Otherwise, print No and return.
- Initialize the variable negative as 0.
- Iterate over the range [0. size) where size is the size of the vector neg[] using the iterator variable p and if negative – p.first is greater than equal to 0 then add p.second to the variable negative. Otherwise, print No and return.
- If the value of open is not equal to negative, then print No. Otherwise, print Yes.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check possible RBS from// the given stringsint checkRBS(vector<string> S){ int N = S.size(); // Stores the values {sum, min_prefix} vector<pair<int, int> > v(N); // Iterate over the range for (int i = 0; i < N; ++i) { string s = S[i]; // Stores the total sum int sum = 0; // Stores the minimum prefix int pre = 0; for (char c : s) { if (c == '(') { ++sum; } else { --sum; } // Check for minimum prefix pre = min(sum, pre); } // Store these values in vector v[i] = { sum, pre }; } // Make two pair vectors pos and neg vector<pair<int, int> > pos; vector<pair<int, int> > neg; // Store values according to the // mentioned approach for (int i = 0; i < N; ++i) { if (v[i].first >= 0) { pos.push_back( { -v[i].second, v[i].first }); } else { neg.push_back( { v[i].first - v[i].second, -v[i].first }); } } // Sort the positive vector sort(pos.begin(), pos.end()); // Stores the extra count of // open brackets int open = 0; for (auto p : pos) { if (open - p.first >= 0) { open += p.second; } // No valid bracket sequence // can be formed else { cout << "No" << "\n"; return 0; } } // Sort the negative vector sort(neg.begin(), neg.end()); // Stores the count of the // negative elements int negative = 0; for (auto p : neg) { if (negative - p.first >= 0) { negative += p.second; } // No valid bracket sequence // can be formed else { cout << "No\n"; return 0; } } // Check if open is equal to negative if (open != negative) { cout << "No\n"; return 0; } cout << "Yes\n"; return 0;}// Driver Codeint main(){ vector<string> arr = { ")", "()(" }; checkRBS(arr); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to check possible RBS from// the given Stringsstatic int checkRBS(String[] S){ int N = S.length; // Stores the values {sum, min_prefix} pair []v = new pair[N]; // Iterate over the range for (int i = 0; i < N; ++i) { String s = S[i]; // Stores the total sum int sum = 0; // Stores the minimum prefix int pre = 0; for (char c : s.toCharArray()) { if (c == '(') { ++sum; } else { --sum; } // Check for minimum prefix pre = Math.min(sum, pre); } // Store these values in vector v[i] = new pair( sum, pre ); } // Make two pair vectors pos and neg Vector<pair> pos = new Vector<pair>(); Vector<pair > neg = new Vector<pair>(); // Store values according to the // mentioned approach for (int i = 0; i < N; ++i) { if (v[i].first >= 0) { pos.add( new pair( -v[i].second, v[i].first )); } else { neg.add( new pair( v[i].first - v[i].second, -v[i].first )); } } // Sort the positive vector Collections.sort(pos,(a,b)->a.first-b.first); // Stores the extra count of // open brackets int open = 0; for (pair p : pos) { if (open - p.first >= 0) { open += p.second; } // No valid bracket sequence // can be formed else { System.out.print("No" + "\n"); return 0; } } // Sort the negative vector Collections.sort(neg,(a,b)->a.first-b.first); // Stores the count of the // negative elements int negative = 0; for (pair p : neg) { if (negative - p.first >= 0) { negative += p.second; } // No valid bracket sequence // can be formed else { System.out.print("No\n"); return 0; } } // Check if open is equal to negative if (open != negative) { System.out.print("No\n"); return 0; } System.out.print("Yes\n"); return 0;}// Driver Codepublic static void main(String[] args){ String []arr = { ")", "()(" }; checkRBS(arr);}}// This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approach# Function to check possible RBS from# the given stringsdef checkRBS(S): N = len(S) # Stores the values {sum, min_prefix} v = [0]*(N) # Iterate over the range for i in range(N): s = S[i] # Stores the total sum sum = 0 # Stores the minimum prefix pre = 0 for c in s: if (c == '('): sum += 1 else: sum -= 1 # Check for minimum prefix pre = min(sum, pre) # Store these values in vector v[i] = [sum, pre] pos = [] neg = [] # Store values according to the # mentioned approach for i in range(N): if (v[i][0] >= 0): pos.append( [-v[i][1], v[i][0]]) else: neg.append( [v[i][0] - v[i][1], -v[i][0]]) # Sort the positive vector pos.sort() # Stores the extra count of # open brackets open = 0 for p in pos: if (open - p[0] >= 0): open += p[1] # No valid bracket sequence # can be formed else: print("No") return 0 # Sort the negative vector neg.sort() # Stores the count of the # negative elements negative = 0 for p in neg: if (negative - p[0] >= 0): negative += p[1] # No valid bracket sequence # can be formed else: print("No") return 0 # Check if open is equal to negative if (open != negative): print("No") return 0 print("Yes")# Driver Codeif __name__ == "__main__": arr = [")", "()("] checkRBS(arr) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ class pair : IComparable<pair> { public int first,second; public pair(int first, int second) { this.first = first; this.second = second; } public int CompareTo(pair p) { return this.first - p.first; } } // Function to check possible RBS from// the given Stringsstatic int checkRBS(String[] S){ int N = S.Length; // Stores the values {sum, min_prefix} pair []v = new pair[N]; // Iterate over the range for (int i = 0; i < N; ++i) { String s = S[i]; // Stores the total sum int sum = 0; // Stores the minimum prefix int pre = 0; foreach (char c in s.ToCharArray()) { if (c == '(') { ++sum; } else { --sum; } // Check for minimum prefix pre = Math.Min(sum, pre); } // Store these values in vector v[i] = new pair( sum, pre ); } // Make two pair vectors pos and neg List<pair> pos = new List<pair>(); List<pair > neg = new List<pair>(); // Store values according to the // mentioned approach for (int i = 0; i < N; ++i) { if (v[i].first >= 0) { pos.Add( new pair( -v[i].second, v[i].first )); } else { neg.Add( new pair( v[i].first - v[i].second, -v[i].first )); } } // Sort the positive vector pos.Sort(); // Stores the extra count of // open brackets int open = 0; foreach (pair p in pos) { if (open - p.first >= 0) { open += p.second; } // No valid bracket sequence // can be formed else { Console.Write("No" + "\n"); return 0; } } // Sort the negative vector neg.Sort(); // Stores the count of the // negative elements int negative = 0; foreach (pair p in neg) { if (negative - p.first >= 0) { negative += p.second; } // No valid bracket sequence // can be formed else { Console.Write("No\n"); return 0; } } // Check if open is equal to negative if (open != negative) { Console.Write("No\n"); return 0; } Console.Write("Yes\n"); return 0;}// Driver Codepublic static void Main(String[] args){ String []arr = { ")", "()(" }; checkRBS(arr);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to check possible RBS from// the given stringsfunction checkRBS(S) { let N = S.length; // Stores the values {sum, min_prefix} let v = new Array(N); // Iterate over the range for (let i = 0; i < N; ++i) { let s = S[i]; // Stores the total sum let sum = 0; // Stores the minimum prefix let pre = 0; for (let c of s) { if (c == "(") { ++sum; } else { --sum; } // Check for minimum prefix pre = Math.min(sum, pre); } // Store these values in vector v[i] = [sum, pre]; } // Make two pair vectors pos and neg let pos = []; let neg = []; // Store values according to the // mentioned approach for (let i = 0; i < N; ++i) { if (v[i][0] >= 0) { pos.push([-v[i][1], v[i][0]]); } else { neg.push([v[i][0] - v[i][1], -v[i][0]]); } } // Sort the positive vector pos.sort((a, b) => a - b); // Stores the extra count of // open brackets let open = 0; for (let p of pos) { if (open - p[0] >= 0) { open += p[1]; } // No valid bracket sequence // can be formed else { document.write("No" + "<br>"); return 0; } } // Sort the negative vector neg.sort((a, b) => a - b); // Stores the count of the // negative elements let negative = 0; for (let p of neg) { if (negative - p[0] >= 0) { negative += p[1]; } // No valid bracket sequence // can be formed else { document.write("No<br>"); return 0; } } // Check if open is equal to negative if (open != negative) { document.write("No<br>"); return 0; } document.write("Yes<br>"); return 0;}// Driver Codelet arr = [")", "()("];checkRBS(arr);// This code is contributed by gfgking.</script> |
Output:
Yes
Time Complexity: O(N*M + N*log(N)), where M is the maximum length of the string in the array arr[].
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!
