Last Updated: 11 Jan, 2021
Longest Valid Parentheses
Moderate
Asked in companies
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.
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
Approaches
- The idea is to generate all the possible substrings of the given string.
- 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.
- Return the length of the longest substring.
The algorithm for the above approach is:
- Generate a substring SUB of the given string.
- Now we need to check if SUB is valid or not. For this, create an empty stack.
- 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.
- After step 3, if the stack is NOT empty, SUB is invalid.
- Otherwise, SUB is valid, update the maximum length if required.
- Repeat the above procedure until all the substrings have been checked.
- The idea is to use the concept of dynamic programming.
- We create a DP array, of size equal to the length of the string, where DP[i] represents the length of the longest valid substring ending at ith index.
- An important point to understand here is that all the valid substrings end with ‘)’ and therefore for the substrings ending with ‘(’, DP[i] will be zero.
- The DP array is updated according to the following conditions:
- Let i be the current index. Check if S[i] = ‘(’, set DP[i] = 0 and move to the next index.
- Otherwise, check if S[i] = ‘)’, there will be two cases :
- If S[i-1] = ‘(‘, then the string is of the form “.......()”. Hence, DP[i] = DP[i-2] + 2.
- Otherwise if S[i-1] = ‘)’, then the string is of the form “.......))”.
- For S[i] to be a part of a valid substring, there must exist a ‘(‘ before the valid substring ending at S[i-1].
- Therefore we check, If S[i - 1 - DP[i-1] ] = ‘(‘: In that case S[i] is part of a larger substring which starts at S[i - 1 - DP[i-1] ]. Hence, DP[i] = DP[i- DP[i-1] - 2] + 1 + DP[i-1] + 1 => DP[i- DP[i-1] - 2] + DP[i-1] + 2.
- Update the maximum length with DP[i], if required.
- In this way, we fill the complete DP array by iterating over the given string, update the maximum length at each step.
- We can avoid checking every substring by making use of a stack.
- The stack will tell us if the string scanned so far is valid or not.
- By pushing the indices, instead of characters, we can also determine the length of the longest valid substring.
Algorithm:
- Start by creating an empty stack and push -1 into it.
- Iterate over the given string.
- Whenever you encounter ‘(‘, push the current index in the stack.
- Whenever you encounter ‘)‘:
- Pop the top index from the stack.
- Now, if the stack is empty, push the current index in it. Otherwise, we have found a valid substring. Find its length by subtracting the current index from the top element.
- Update the maximum length if required.
- This requires us to use two counters: L and R.
- Initialise the counters to zero.
- Firstly, we traverse the string from left to right, incrementing L whenever we encounter ‘(‘ and incrementing R whenever we encounter ‘)‘.
- When L and R become equal, we have found a valid substring (as it contains equal number of ‘(‘ and ‘)’ characters and is well-formed). So, update the maximum length, if required.
- When R becomes greater than L, it means we have more ‘)’ than ‘(‘ in our substring, this cannot be a valid substring. Hence, we reset R and L to zero, equivalent to making the substring empty.
- After traversing the string from left to right above procedure is repeated, by traversing the string from right to left.
- This is done because it is possible to miss the longest substring while we traverse left to right.
- For example, the string “(()()” will give zero maximum length in the forward pass, as L and R never become equal, whereas the answer is 4 (i.e. “()()”).
- To correct this we do a backward pass as well.
- A point to note here is that, while traversing the string from right to left, we reset R and L only when L becomes greater than R, the rest of the steps remain unchanged.
Similar problems