New update is available. Click here to update.

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