*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #32 (*Hard*): Longest Valid Parentheses

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

Given a string containing just the characters

`'('`

and`')'`

, find the length of the longest valid (well-formed) parentheses substring.

####
*Examples:*

*Examples:*

Example 1: Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()".

Example 2: Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()".

Example 3: Input: s = "" Output: 0

####
*Constraints:*

*Constraints:*

- 0 <= s.length <= 3 * 10^4
- s[i] is '(', or ')'.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

One of the key things to realize about valid parentheses strings is that they're entirely self-satisfied, meaning that while you can have one substring that is entirely inside another, you can't have two substrings that only partially overlap.

This means that we can use a **greedy O(N) time complexity** solution to this problem without the need for any kind of backtracking. In fact, we should be able to use a very standard stack-based valid parentheses string algorithm with just three very minor modifications.

In a stadard valid parentheses string algorithm, we iterate through the string (**S**) and push the index (**i**) of any **'('** to our **stack**. Whenever we find a **')'**, we match it with the last entry on the **stack** and pop said entry off. We know the string is not valid if we find a **')'** while there are no **'('** indexes in the **stack** with which to match it, and also if we have leftover **'('** in the **stack** when we reach the end of **S**.

For this problem, we will need to add in a step that updates our answer (**ans**) when we close a parentheses pair. Since we stored the index of the **'('** in our stack, we can easily find the difference between the **')'** at **i** and the last entry in the **stack**, which should be the length of the valid substring which was just closed.

But here we run into a problem, because consecutive valid substrings can be grouped into a larger valid substring (ie, **'()()' = 4**). So instead of counting from the *last* **stack** entry, we should actually count from the *second to last* entry, to include any other valid closed substrings since the most recent **'('** that will still remain after we pop the just-matched last **stack** entry off.

This, of course, brings us to the second and third changes. Since we're checking the second to last **stack** entry, what happens in the case of **'()()'** when you close the second valid substring yet there's only the one **stack** entry left at the time?

To avoid this issue, we can just wrap the entire string in another imaginary set of parentheses by starting with **stack = [-1]**, indicating that there's an imaginary **'('** just before the beginning of the string at **i = 0**.

The other issue is that we will want to continue even if the string up to **i** becomes invalid due to a **')'** appearing when the **stack** is "empty", or in this case has only our imaginary index left. In that case, we can just effectively restart our **stack** by updating our imaginary **'('** index (**stack[0] = i**) and continue on.

Then, once we reach the end of **S**, we can just **return ans**.

####
*Implementation:*

*Implementation:*

There are only minor differences in the code for all four languages.

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var longestValidParentheses = function(S) {
let stack = [-1], ans = 0
for (let i = 0; i < S.length; i++)
if (S[i] === '(') stack.push(i)
else if (stack.length === 1) stack[0] = i
else stack.pop(), ans = Math.max(ans, i - stack[stack.length-1])
return ans
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def longestValidParentheses(self, S: str) -> int:
stack, ans = [-1], 0
for i in range(len(S)):
if S[i] == '(': stack.append(i)
elif len(stack) == 1: stack[0] = i
else:
stack.pop()
ans = max(ans, i - stack[-1])
return ans
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int longestValidParentheses(String S) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int ans = 0;
for (int i = 0; i < S.length(); i++)
if (S.charAt(i) == '(') stack.push(i);
else {
stack.pop();
if (stack.isEmpty()) stack.push(i);
else ans = Math.max(ans, i - stack.peek());
}
return ans;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
int longestValidParentheses(string S) {
vector<int> stack = {-1};
int ans = 0;
for (int i = 0; i < S.size(); i++)
if (S[i] == '(') stack.push_back(i);
else if (stack.size() == 1) stack[0] = i;
else {
stack.pop_back();
ans = max(ans, i - stack.back());
}
return ans;
}
};
```

## Discussion (4)

Can you elaborate what do you mean by this " you can't have two substrings that only partially overlap." ? Appreciate your help :)

Sure! If you find a valid parentheses substring in

S, you cannot possibly find another one that starts inside, but ends outside, the first one. In order for that to be the case, you'd have to have an unmatched parenthesis in the first substring, which would make that substringnotvalid, by definition.That makes a big difference, because it means we don't need to check every index as a starting point for a valid parentheses substring, which would be

O(N^2) time. We can instead use agreedyapproach inO(N) time.Since valid substrings can

fully containother valid substrings, however, we need the help of astack.Hey there, just wanted to clarify what "longest valid" means. if

`S = '())()()'`

would the longest be`'()'`

,`'()()'`

, or`'()()()'`

?Ah okay,

`'()()'`

would be the answer, never mind!