Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Longest Valid Parentheses

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
15 upvotes
Asked in companies
OlaGoogleAmazon

Problem statement

You are given a string ‘S’ containing only the characters ‘)’ and ‘(‘. You need to find the length of the longest valid i.e. well-formed parentheses substring.

For example:
Let the given string be “(()())((”.

Here the valid parentheses substrings are: “()”, “()” and “(()())”. Out of these the longest valid string is “(()())” which has a length 6.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 100   
1 <= Length(S) <= 10^4

Where ‘T’ is the number of test cases and ‘S’ is the given string.

Time Limit: 1sec
Sample Input 1:
2
)()()))
)))(((
Sample Output 1:
4
0
Explanation For Sample Input 1:
For the first test case, the longest valid (well-formed) parentheses substring is “()()” with length 4.

For the second test case, there is no valid parentheses substring. Hence, the output is 0.
Sample Input 2:
2
()((())()
()()()()()()()
Sample Output 2:
6
14
Full screen
Console