Longest Valid Substring

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in companies
AmazonHCL TechnologiesMorgan Stanley

Problem statement

You are given a string 'STR' consisting only of opening and closing parenthesis i.e. '(' and ')', your task is to find out the length of the longest valid parentheses substring.

Note: 
The length of the smallest valid substring '()' is 2.
For example: 
'STR' = “()()())” here we can see that except the last parentheses all the brackets are making a valid parenthesis. Therefore, the answer for this will be 6.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer 'T' denoting the number of test cases.

The first and the only line of each test case contains a string ‘str’ of which you have to tell the longest valid parentheses substring.
Output format : 
For each test case, return a single integer which is the length of the longest valid substring.
Note: 
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= |STR| <= 3000

where |STR| is the length of the given string.

Time Limit: 1 sec
Sample Input 1 :
2
()))((())
))((
Sample Output 1 :
4
0
Explanation For Sample Input 1:
For the first test case:
Given 'STR' =”()))((())”, we can see that from index 5 to the last, the whole substring is valid. Therefore, the length of the longest valid parentheses substring is 4.


For the second test case:
Given 'STR' =”))((”, we can see that there is no valid substring present in the string. o, the answer will be 0.
Sample Input 2 :
2
()))((((()))))) 
)(()
Sample Output 2 :
10
2
Hint

Can you check for all the possible substrings?

Approaches (2)
Brute - force

The idea is to check for all the substrings of the given string and then check for each substring whether it is valid or not.

 

  • Run two nested loops for generating the indices of all the substrings of the string say i and j (i starting from 0 and j starting from i).
    • Take the substring from index i to j.
    • Check for the validity of this substring.
    • For this, make a function isValid and pass a string in this function to check for its validity.
      • Declare a stack 'stk'.
      • Now traverse the given string.
      • If the character in the string is the starting bracket, then push it to the stack.
      • If the character is a closing bracket then pop from the stack and if the popped character is the opening bracket, then it is fine else brackets are not valid.
      • After the string is completely traversed if there are any braces left in the stack that also means that the string is invalid.
  • After this function is called for every substring, if the string is valid then just update the length of the maximum valid substring.
  • Finally, return the maximum length of the valid substring.
Time Complexity

O(N ^ 3), where ‘N’ denotes the length of the given string.

 

Since we are calculating all possible substrings of the string and then we are calculating the validity of each substring. So, the time complexity will be O(N ^ 3)(for calculating every substring) + O(N)(for its validity) = O(N ^ 3).

Space Complexity

O(N), where ‘N’ denotes the length of the given string.

 

Since we are using a stack for storing the string characters, the net space complexity will be O(N).

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