32. Longest Valid Parentheses

Description

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

longest-valid-parentheses.py

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        opened = []
        mp = [False] * n

        for i, c in enumerate(s):
            if c == "(":
                opened.append(i)
            else:
                if opened:
                    mp[opened.pop()] = True
                    mp[i] = True

        res = total = i = 0
        while i < n:
            if i + 1 < n and mp[i] and mp[i+1]:
                total += 2
                i += 2
            else:
                total = 0
                i += 1

            res = max(res, total)

        return res