Longest Valid Parentheses

Palindrome Number

Median of Two Sorted Arrays

Measure the longest contiguous substring of balanced parentheses.

Return the length of the longest contiguous substring of `s` that is a well-formed parentheses sequence.

**Input / output**
- Input: `s: string`
- Output: integer length

**Examples**
1. `"(()"` returns `2`.
2. `")()())"` returns `4` from `"()()"`.

**Constraints**
- `0 <= s.length <= 100,000`
- `s` contains only `(` and `)`

**Follow-up**
Compare stack, dynamic-programming, and two directional counter scans.

- A valid parentheses substring must have every closing parenthesis matched with a previous opening parenthesis.
- When a closing parenthesis cannot be matched, any substring crossing it is invalid.
- We need a way to remember the most recent invalid boundary and unmatched opening positions.

Track Valid Substring Boundaries

- Store indexes rather than characters so lengths are easy to compute.
- Start the stack with `-1`, a sentinel boundary before the string begins.
- Push indexes of `(` characters because they may match future `)` characters.

Use a Stack of Indexes

- For `)`, pop one index because it attempts to close the most recent unmatched `(`.
- If the stack becomes empty, this `)` is unmatched, so push its index as the new invalid boundary.
- Otherwise, the current valid substring starts after `stack[-1]`.

Handle Closing Parentheses

- After a successful match, `stack[-1]` is the index just before the current valid substring.
- The substring from `stack[-1] + 1` through `i` is therefore valid.
- Its length is `i - stack[-1]`.

Why the Length Formula Works

- The sentinel handles valid substrings that start at index 0.
- Resetting the sentinel after an unmatched `)` handles broken regions.
- Time complexity is O(n), and extra space complexity is O(n).