Longest Bracket

Moderate
0/80
Average time to solve is 20m
10 upvotes
Asked in company
Walmart

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )

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.

##### Sample Input 1:

2
)((())))(()())
))(
Sample Output 1 :
6 2
0 1
Explanation for Sample Input 1 :
Test Case 1:
The longest balanced parentheses substring starts from index 1 and ends at index 6 making the count of longest substring 6 and there is another balanced substring of length = 6 starting from index 8 and ending at index 13.

Therefore, the total count of balanced parentheses substring is 2. Hence the output is “6 2”.

Test Case 2: 
 There is no such balanced parentheses substring exists in the input string so the length of the longest balanced parentheses substring is 0 and 1 will be the count of such substring.

##### Sample Input 2 :

2
)()()()()()()
(())(
Sample Output 2 :
12 1
4 1
Explanation for Sample Input 1 :
Test Case 1:
The longest balanced parentheses substring starts from index 2 and ends at index 13 with length  = 12 and total count 1.

Test Case 2: 
The longest balanced parentheses substring starts from index 1 and ends at index 4 with length  = 4 and total count 1.
Hint

Try to think of using some extra data structure .

Approaches (1)
Stack Approach

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.
Time Complexity

O(N), where ‘N’ is the length of the given string.

 

As we are traversing the input string in linear time. Therefore, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the length of the given string.

 

As we are using auxiliary space for ‘closing[]’, ‘opening[]’ and for the stack. Therefore O(3 * N) space is used. Therefore, overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Longest Bracket
Full screen
Console