Longest Valid Parentheses

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
19 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 )
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases.

The first and the only line of every test case contains the string S.
Output Format:
For each test case, the length of the longest valid (well-formed) parentheses substring is printed.

The output for each test case is printed in a separate line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.
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
Hint

Can you solve it by generating all the possible substrings?

Approaches (4)
Generate All Possible Substrings
  1. The idea is to generate all the possible substrings of the given string.
  2. For each substring check if it is valid or not.
    • This can be checked by using a stack.
    • If it is valid, check if its length is greater than the previously generated valid substrings. If so, update the maximum length.
  3. Return the length of the longest substring.

 

The algorithm for the above approach is:

  1. Generate a substring SUB of the given string.
  2. Now we need to check if SUB is valid or not. For this, create an empty stack.
  3. Iterate over the substring:
    • If the current character is ‘(‘, Push it in the stack.
    • Otherwise, If the current character is ‘)’
      • If the stack is empty, SUB is invalid.
      • Otherwise, Pop an element from the stack.
  4. After step 3, if the stack is NOT empty, SUB is invalid.
  5. Otherwise, SUB is valid, update the maximum length if required.
  6. Repeat the above procedure until all the substrings have been checked.
Time Complexity

O(Length(S) ^ 3) per test case, where S is the given string.

 

In the worst case, we are generating all the possible substrings of string S. Generation of each substring requires approximately constant time. For a string S there are (Length(S) * (Length(S) +1)) / 2 possible substrings. For each substring we check if it is valid or not, which requires O(Length(S)) operations. Hence the overall time complexity is O((Length(S) * (Length(S) + 1))/2) * O(Length(S))). = O(Length(S) ^ 3).

Space Complexity

O(Length(S)) per test case, where S is the given string.

 

In the worst case, O(Length(S)) extra space is required by the stack.

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