32 - Longest Valid Parentheses

Difficulty: Hard | Pattern: Stack / Dynamic Programming | Company tags: Amazon, Google, Microsoft

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  ("()" is the longest)

Example 2:

Input: s = ")()())"
Output: 4  ("()()" is the longest)

Example 3:

Input: s = ""
Output: 0

Approach 1: Stack — O(n), O(n)

Key insight: Push index of ( onto stack. When ) matches, pop and compute length. Stack bottom is a "fence" — initialize with -1.

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    max_len = 0
    
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # unmatched ')' becomes new fence
            else:
                max_len = max(max_len, i - stack[-1])
    
    return max_len

Approach 2: Two Passes (L→R and R→L) — O(n), O(1)

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

Dry Run

s = ")()())"

Stack: init=[-1]

i	c	stack	max_len
0	)	pop -1, empty→push 0	0
1	(	push 1	0
2	)	pop 1, stack=[-1] → i-(-1)=3-1=2	2
3	(	push 3	2
4	)	pop 3, stack=[0] → i-0=4	4
5	)	pop 0, empty→push 5	4

Result: 4 ✓

Complexity

• Time: O(n)
• Space: O(n) stack; O(1) two-pass