2026-09-24 — Longest Valid Parentheses

Push indices of every (. On a ), pop one opener and measure the run: i - stack[-1] is the length of the valid substring ending at i, because everything between that ) and the previous unmatched index is now matched. When the stack runs empty, the current ) is itself the new "wall" — push it as the base for future measurements.

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]          # base index: everything after it is a candidate run
    best = 0

    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()                    # match this ")" with the last "("
            if stack:
                best = max(best, i - stack[-1])
            else:
                stack.append(i)            # unmatched ")" becomes the new base

    return best

How it works. The stack always ends with a base index — the position of the most recent ) that could not be matched (initially a virtual -1 before the string). Everything after the base is either matched or an unmatched (. On a ):

• Pop the most recent (. If something remains, the top is the base, and i - base is exactly the length of the valid run ending at i: the opener we just popped closes a pair, and every character between the base and i is part of that matched run.
• If the stack is empty, this ) matched nothing — it is now the new base.

Complexity. Time: O(n) — each index is pushed and popped at most once. Space: O(n) — the stack.

Edge cases that matter. A single ) (base moves to 0, answer 0). A string of only openers (stack fills, no ) ever fires, answer 0). The ")()())" shape where the answer is inside an outer unmatched pair — the base at index 0 makes i - base measure from the right place.

Common wrong answer. Counting total matched pairs and multiplying by 2 — that gives the length of the valid characters overall, not of the longest contiguous valid run. On ")()())" it would also say 4 by luck, but on "())())" it says 4 while the true contiguous answer is 2.

O(1)-space variant (mention it). Scan left-to-right with open and current counters: a ( increments open, a ) with open > 0 closes a pair (open -= 1; current += 2), a ) with open == 0 resets both. That misses runs that are longer on the left ("(()"), so scan right-to-left symmetrically and take the max of the two passes.