Longest Balanced Substring

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
Nagarro SoftwareGoogle inc

Problem statement

You are given a string STR containing just two characters ‘(‘ and ‘)’. You have to find the length of the longest balanced substring in the given string. String ‘B’ is a substring of string ‘A’ if it can be obtained from ‘A’ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters ‘+’ and ‘1’. For example, sequences ‘(())()’, ‘()’ and ‘(()(()))’ are balanced, while ‘)(‘, ‘(()’ and ‘(()))(‘ are not.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow.

The first line and only line of each test case contain a string STR containing just two characters ‘(‘ and ‘)’.
Output Format : 
For every test case, print an integer denoting the length of the longest balanced substring.

The output of each test case is printed in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= |STR| <= 5 * 10^4

Where |STR| is the length of the string.

Time Limit: 1 sec
Sample Input 1:
2
))(())
()()()
Sample Output 1:
4
6
Explanation for Sample Input 1:
In the 1st test case, “(())” is the longest substring that is balanced.

In the 2nd test case, the whole string is balanced.
Sample Input 2:
2
()(())
()
Sample Output 2:
6
2
Hint

For each substring, check if it can be the longest balanced substring.

Approaches (5)
Brute-Force

In this approach, we will consider every substring and check if it can be the longest balanced substring. 

 

Below is the detailed approach: 

 

  1. Initialize a variable ‘ANS’ = 0, this will store the length of the longest balanced substring.
  2. Run a for loop from 0 to |'S'| - 1, where |'S'| is the length of string (say iterator = ‘i’):
    • Run a for loop from ‘i’ to |'S'| - 1, where |'S'| is the length of string (say iterator = ‘j’):
      • If substring(‘i’, ‘j’) is balanced, then:
        • ‘ANS’ = max (‘ANS’ , ‘j’ - ‘i’ + 1).
  3. Finally, return ‘ANS’.

 

To check if a string is balanced or not, follow the below steps:

 

  1. Make two variables ‘O’(count of open parentheses) and ‘C’ (count of close parentheses) and initialize them with zero.
  2. Now iterate on the string, if the ith character is ‘(‘, increment ‘O’, else increment ‘C’.
  3. If at any index ‘C’ becomes greater than ‘O’ or ‘O’ becomes greater than N, then the sequence is not balanced.
  4. In the end, if ‘O’ is equal to ‘C’, then the string is balanced.
Time Complexity

O(N^3), Where N is the length of the given string.
 

It takes O(N^2) to consider every substring and in the worst case, it will take O(N) time to check if a substring is balanced or not. Thus, the final time complexity is O(N * N * N) = O(N^3).

Space Complexity

O(1)
 

Constant additional space is required.

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