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 the string must have count of ‘(‘ greater than or equal to count of ‘)’ and count of ‘(‘ and ‘)’ are equal in the whole string. For Examples: “(())”, “()((()))”, …, etc
Examples:
Input: arr[] = {“) ( ) )”, “)”, “( (“, “( (“, “(“, “)”, “)”}
Output: 2
Explanation:
Following are the pair of strings:
- (2, 1): The string at indices are “((“ and “)())”. Now, the concatenation of these string is “(()())” which is a regular bracket sequence.
- (4, 5): The string at indices are “(“ and “)”. Now, the concatenation of these string is “()” which is a regular bracket sequence.
Therefore, the total count of pairs of regular bracket sequence is 2.
Input: arr[] = {“( ( ) )”, “( )”}
Output: 1
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs of strings from the given array and count those pairs whose concatenation results in the Regular Bracket Sequence. After checking for all possible pairs, print the total count obtained.
Time Complexity: O(L*N2), where L is the maximum length of the string.
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by describing each string by a pair (A, B), where A and B are the smallest values such that after adding A opening parentheses “(“ to the left of the string and B closing parentheses “)” to the right of the string it becomes a regular bracket sequence. To concatenate two-bracket sequences (say, ith and jth) in order to produce a correct bracket sequence, the excess of the opening parentheses in the i-th sequence must equal the excess of the closing parentheses in the jth sequence; that is, bi = aj. Follow the steps below to solve the problem:
- Initialize two arrays, say open[] and close[] to 0. Also, initialize an integer variable ans to 0 that stores the resultant count of pairs.
- Traverse the given array and perform the following steps:
- Find the number of opening and closing parentheses needed to be added to the left and right of arr[i] respectively to make arr[i] a regular bracket sequence using the approach discussed in this article. Let the values be a and b respectively.
- If a!=0 and b!=0 then arr[i] will require parenthesis on both of its sides so it is not possible to concatenate it with any other string.
- If a==0 and b==0 then this particular string is already a regular bracket sequence and can be paired with other strings which are regular bracket sequences.
- Otherwise, if a is equal to 0, then increment close[b] by 1 else increment open[a] by 1.
- Add the value of floor of (close[0]/2) to the value of ans.
- Traverse the array open[] and add the value of a minimum of open[i] and close[i] to the variable ans.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:-
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;void countPairs(int N, vector<string>arr){ // Stores the count of opening // and closing parenthesis for // each string arr[i] vector<int>open(100,0); vector<int>close(100,0); // Stores maximum count of pairs int ans = 0; // Traverse the array arr[] for(int i = 0; i < N; i++){ vector<char>c; for(auto j : arr[i]){ c.push_back(j); } int d = 0; int minm = 0; // Traverse the string c[] for(int j = 0; j < c.size(); j++){ // Opening Bracket if (c[j] == '(') d += 1; // Otherwise, Closing // Bracket else{ d -= 1; if (d < minm) minm = d; } } // Count of closing brackets // needed to balance string if (d >= 0){ if (minm == 0) close[d]++; } // Count of opening brackets // needed to balance string else if (d < 0){ if (minm == d) open[-d]++; } } // Add the count of balanced // sequences ans += floor(close[0]/2); // Traverse the array for(int i = 1; i < 100; i++) ans +=min(open[i], close[i]); // Print the resultant count cout<<ans<<endl;}// Driver Codeint main(){ int N = 7; vector<string>list; list.push_back(")())"); list.push_back(")"); list.push_back("(("); list.push_back("(("); list.push_back("("); list.push_back(")"); list.push_back(")"); countPairs(N, list);}// This code is contributed by shinjanpatra |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to count the number of // pairs whose concatenation results // in the regular bracket sequence static void countPairs( int N, ArrayList<String> arr) { // Stores the count of opening // and closing parenthesis for // each string arr[i] int open[] = new int[100]; int close[] = new int[100]; // Stores maximum count of pairs int ans = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { char c[] = arr.get(i).toCharArray(); int d = 0; int min = 0; // Traverse the string c[] for (int j = 0; j < c.length; j++) { // Opening Bracket if (c[j] == '(') { d++; } // Otherwise, Closing // Bracket else { d--; if (d < min) min = d; } } // Count of closing brackets // needed to balance string if (d >= 0) { if (min == 0) close[d]++; } // Count of opening brackets // needed to balance string else if (d < 0) { if (min == d) open[-d]++; } } // Add the count of balanced // sequences ans += close[0] / 2; // Traverse the array for (int i = 1; i < 100; i++) { ans += Math.min( open[i], close[i]); } // Print the resultant count System.out.println(ans); } // Driver Code public static void main(String[] args) { int N = 7; ArrayList<String> list = new ArrayList<String>(); list.add(")())"); list.add(")"); list.add("(("); list.add("(("); list.add("("); list.add(")"); list.add(")"); countPairs(N, list); }} |
Python3
# Python3 program for the above approach# Function to count the number of# pairs whose concatenation results# in the regular bracket sequencedef countPairs(N, arr): # Stores the count of opening # and closing parenthesis for # each string arr[i] open = [0] * 100 close = [0] * 100 # Stores maximum count of pairs ans = 0 # Traverse the array arr[] for i in range(N): c = [i for i in arr[i]] d = 0 minm = 0 # Traverse the string c[] for j in range(len(c)): # Opening Bracket if (c[j] == '('): d += 1 # Otherwise, Closing # Bracket else: d -= 1 if (d < minm): minm = d # Count of closing brackets # needed to balance string if (d >= 0): if (minm == 0): close[d] += 1 # Count of opening brackets # needed to balance string elif (d < 0): if (minm == d): open[-d] += 1 # Add the count of balanced # sequences ans += close[0] // 2 # Traverse the array for i in range(1, 100): ans +=min(open[i], close[i]) # Print the resultant count print(ans)# Driver Codeif __name__ == '__main__': N = 7 list = [] list.append(")())") list.append(")") list.append("((") list.append("((") list.append("(") list.append(")") list.append(")") countPairs(N, list)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count the number of// pairs whose concatenation results// in the regular bracket sequencestatic void countPairs(int N, List<string> arr){ // Stores the count of opening // and closing parenthesis for // each string arr[i] int[] open = new int[100]; int[] close = new int[100]; // Stores maximum count of pairs int ans = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { char[] c = arr[i].ToCharArray(); int d = 0; int min = 0; // Traverse the string c[] for(int j = 0; j < c.Length; j++) { // Opening Bracket if (c[j] == '(') { d++; } // Otherwise, Closing // Bracket else { d--; if (d < min) min = d; } } // Count of closing brackets // needed to balance string if (d >= 0) { if (min == 0) close[d]++; } // Count of opening brackets // needed to balance string else if (d < 0) { if (min == d) open[-d]++; } } // Add the count of balanced // sequences ans += close[0] / 2; // Traverse the array for(int i = 1; i < 100; i++) { ans += Math.Min(open[i], close[i]); } // Print the resultant count Console.WriteLine(ans);}// Driver Codepublic static void Main(string[] args){ int N = 7; List<string> list = new List<string>(); list.Add(")())"); list.Add(")"); list.Add("(("); list.Add("(("); list.Add("("); list.Add(")"); list.Add(")"); countPairs(N, list);}}// This code is contributed by ukasp |
Javascript
<script>// JavaScript program for the above approach// Function to count the number of// pairs whose concatenation results// in the regular bracket sequencefunction countPairs(N, arr){ // Stores the count of opening // and closing parenthesis for // each string arr[i] let open = new Array(100).fill(0) let close = new Array(100).fill(0) // Stores maximum count of pairs let ans = 0 // Traverse the array arr[] for(let i = 0; i < N; i++){ let c = []; for(let j of arr[i]){ c.push(j); } let d = 0 let minm = 0 // Traverse the string c[] for(let j = 0; j < c.length; j++){ // Opening Bracket if (c[j] == '(') d += 1 // Otherwise, Closing // Bracket else{ d -= 1 if (d < minm) minm = d } } // Count of closing brackets // needed to balance string if (d >= 0){ if (minm == 0) close[d]++ } // Count of opening brackets // needed to balance string else if (d < 0){ if (minm == d) open[-d]++ } } // Add the count of balanced // sequences ans += Math.floor(close[0]/2) // Traverse the array for(let i = 1; i < 100; i++) ans +=Math.min(open[i], close[i]) // Print the resultant count document.write(ans)}// Driver Code let N = 7let list = []list.push(")())")list.push(")")list.push("((")list.push("((")list.push("(")list.push(")")list.push(")")countPairs(N, list)// This code is contributed by shinjanpatra</script> |
Output:
2
Time Complexity: O(L*N), where N is the maximum length of the string.
Auxiliary Space: O(L)
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!
