Longest Balanced Substring

Posted: 8 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

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
Approach 1

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.
Try Problem