Longest Bracket

Posted: 28 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a string S, consisting of only '(' and ')' characters. You need to find the length of the longest substring which is a regular bracket sequence and also find the count of such substrings with the same length.

Note:

A bracket sequence is called regular, if parenthesis in the given expression is balanced.  For example '()()', '(())' are the regular string but '((()' is not a regular parenthesis string.

If no such substring exists, print "0 1" (without quotes).

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows. 

Each line of the test case contains a string having characters ‘(‘ or ‘)’ in it.
Output format :
For each test case print, 2 space-separated integers representing the length of the longest substring with regular bracket sequence and the number of such substrings present in the input string.

Note:

Update the length of the longest regular bracket substring in the variable ‘length’ and store the count of such substring in variable ‘count’ passed as parameters in the given function.
Constraints :
1 <= T <= 5
1 <= N <= 10 ^ 4


Time Limit : 1 sec.

Note :

You don’t need to print anything, it has already been taken care of. Just implement the given function.
Approach 1

The idea is to store the indices of the opening and closing brackets of the regular expression and then to count the length of the longest regular parentheses subsequence in the given string along with the count of such regular parentheses subsequence having the same length.

 

Approach :

 

  • First of all, for each closing bracket in our string let's define 2 values:
    • opening[j] = position of corresponding open bracket, or INT_MAX if the closing bracket doesn't belong to any regular bracket sequence.
    • closing[j] = position of earliest balanced opening bracket, such that substring of ‘inputString[closing[j], j]’ is a regular bracket sequence. Let's consider closing[j] to be INT_MAX if the closing bracket doesn't belong to any regular bracket sequence.
  • ‘closing[j]’ defines the beginning position of the longest regular bracket sequence, which will end in position j.
  • Both ‘opening[j’] and closing[j] can be found with the following algorithm, which uses the stack.
  • Iterate through the characters of the string.
    • If the current character is an opening bracket, put its index into the stack.
    • If the current character is a closing bracket, there are 2 subcases:
      • Stack is empty - this means that the current closing bracket doesn't have a corresponding open one. Hence, both opening[j] and closing[j] are equal to  INT_MAX.
      • If the Stack is not empty - we will have the position of the corresponding open bracket on the top of the stack - put it to ‘opening[j]’ and remove this position from the stack.
      • Now ‘closing[j]’ is equal to either opening[j] or there can be a better value for closing[j] (some earlier continuous balance). It will be the position opening[j] - 1. If there is a closing bracket at this position, and closing[opening[j] - 1] is not INT_MAX, then we have 2 regular bracket sequences inputstring(closing[opening[j] - 1] to opening[j] - 1)  +  inputstring(opening[j], j),  which can be concatenated into one larger regular bracket sequence. so we put closing[j] to be closing[opening[j] - 1] for this case.
Try Problem