Longest valid parentheses

Given a string of ( and ), return the length of the longest substring that is a well-formed parenthesis sequence.

Before you code

Matching brackets tells you which pairs close, but not how long the valid run is. If the stack holds indexes, every match can measure the distance back to the last position that is not part of the current valid run.

Hints

1. Start the stack with -1, a marker meaning "the valid run starts after this index".
2. For (, push its index.
3. For ), pop. If the stack is now empty, this ) is unmatched: push its index as the new marker. Otherwise, the current valid run has length i - stack[-1].
4. Track the maximum length seen.

Production & complexity notes

When solving Longest valid parentheses on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Stacks and the LIFO rule to reinforce the underlying pattern.

What it practices

Pushing indexes to measure distances, from Stacks and the LIFO rule.