# Longest Valid Parentheses

Posted: 11 Jan, 2021

Difficulty: Moderate

#### 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
```

Approach 1

- 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.

- If the stack is empty,

- 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.

Approach 2

- 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.**

- For
- 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.

Approach 3

- 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.

Approach 4

- 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.