Check if a Regular Bracket Sequence can be formed with concatenation of given strings

0 0 9 minutes read

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 strings
int 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 Code
int main()
{
    vector<string> arr = { ")", "()(" };
    checkRBS(arr);
 
    return 0;
}

Java

// Java program for the above approach
import 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 Strings
static 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 Code
public 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 strings
def 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 Code
if __name__ == "__main__":
 
    arr = [")", "()("]
    checkRBS(arr)
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using 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 Strings
static 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 Code
public 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 strings
function 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 Code
 
let 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 zambiatek!