0032: Longest Valid Parentheses

Problem Statement

Given a string containing just the characters '(' and ')', return 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 ')'.

Code Solution

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stk = [-1]
        
        cmax = 0
        for cx, c in enumerate(s):
            if c == '(':
                stk.append(cx)
            else:
                stk.pop()
                if not stk:
                    stk.append(cx)
                else:
                    cmax = max(cmax, cx - stk[-1])
        
        return cmax