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

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

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