visual walkthrough
Longest Valid Parentheses
Uses stack indices to measure valid spans, with a DP alternative.
The idea
Keep a stack of indices. The index on top is the last place that can't be part of the current valid run. A '(' is pushed; a ')' pops, and the distance from the new top tells how long the valid run ending here is.
If a ')' empties the stack, it can't match anything, so it becomes the new base.
Complexity
| approach | time | space |
|---|---|---|
| Check every substring | O(n³) | O(1) |
| Stack of indices | O(n) | O(n) |