32. Longest Valid Parentheses

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

def longestValidParentheses(self, s: str) -> int:
    from collections import deque
    q = deque()
    longest = 0
    
    q.append(-1)

    for i, c in enumerate(s):
        if c == '(':
            q.append(i)
        else:
            q.pop()
            if not q:
                q.append(i)
            else:
                longest = max(i - q[-1], longest)
                
    return longest

Another simpler idea. Scan from left and then scan from right.

def longestValidParentheses(self, s: str) -> int: 
    m = left = right = 0 
    for i in s: 
        if i == '(': 
            left += 1 
        else: 
            right += 1 
        if left == right: 
            m = max(m, right + left) 
        elif right > left: 
            left = right = 0 

    left = right = 0 
    for i in s[::-1]: 
        if i == ')': 
            right += 1 
        else: 
            left += 1 
        if left == right: 
            m = max(m, right + left) 
        elif left > right: 
            left = right = 0 
    return m