# 32. Longest Valid Parentheses

#### Hard

***

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

 

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

* `0 <= s.length <= 3 * 104`
* `s[i]` is `'('`, or `')'`.

#### Solution 1&#x20;

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        length = 0
        for index, char in enumerate(s):
            if char == "(":
                stack.append(index)
            else:
                stack.pop()
                if not stack:
                    stack.append(index)
                else:
                    length = max(length, index - stack[-1])
        return length
```

#### Solution 2

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        self.length = 0
        left, right = 0, 0
        for char in list(s):
            if char == '(':
                left += 1
            else:
                right += 1
            if left == right:
                self.length = max(self.length, 2*left)
            elif right > left:
                left, right = 0,0
                
        left, right = 0, 0
        for char in list(s[::-1]):
            if char == '(':
                left += 1
            else:
                right += 1
            if left == right:
                self.length = max(self.length, 2*left)
            elif left > right:
                left, right = 0,0
        return self.length
 
```