Longest Valid Parentheses [LC32]

Given a string containing just the characters ‘(‘ and ‘)’, return the length of the longest valid (well-formed) parentheses substring

Using stack

def longest_valid_parentheses(self, s: str) -> int:
    ans = 0
    stack = [-1]
    for i in range(len(s)):
        if s[i] == "(":
            stack.append(i)
        else:
            stack.pop()
            if stack:
                ans = max(ans, i - stack[-1])
            else:
                stack.append(i)
    return ans

Time Complexity

Using 2 pointers

One of the passes will catch all the longest substring. Check the counter comparison condition and order of the comparisons.

def longest_valid_parentheses(self, s: str) -> int:
    left, right = 0, 0
    ans = 0
    for c in s:
        if c == '(':
            left += 1
        else:
            right += 1
            
        if right == left:
            ans = max(ans, 2*right)
        elif right > left:
            left = right = 0
    
    left = right = 0
    for c in reversed(s):
        if c == '(':
            left += 1
        else:
            right += 1

        if right == left:
            ans = max(ans, 2*right)
        elif left > right:
            left = right = 0
    return ans

Time Complexity