Last Updated: 23 Feb, 2021
Longest Valid Substring
Moderate
Asked in companies
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.
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
Approaches
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.
The idea is to store indices of previous starting brackets in a stack. The first element of the stack is an element that provides an index before the beginning of the valid substring that is the base for the next valid substring.
- Declare a stack stk.
- Push -1 for the first element. It provides the base for the next valid substring.
- Declare the max length as zero.
- If the current character in the string is the starting bracket, then push the current index, ( say 'i' ) to the stack.
- If the character is a closing bracket:
- Pop the index from the stack.
- If the stack is not empty, then find the length of the current valid parentheses substring by taking the difference between the current index i and the top of the stack.
- Update the max length in every iteration.
- If the stack is empty then just push the current index in the iteration for the base for the next valid substring.
- Return the max length.