Longest Valid Parentheses
The key idea
Keep a stack of indices and seed it with a
-1 base marker. Push the index of every (. On a ), pop one entry: if the stack is now empty, this ) is unmatched, so push its index as the new base; otherwise the current valid run reaches from just past the new top to i, giving length i - stack.top(). The base marker turns a length into a simple index subtraction.Problem
Given a string s containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
A substring is valid when every '(' has a matching ')' that closes it and the pairs are properly nested. The substring must be contiguous — you cannot skip characters in the middle.
Constraints
0 <= s.length <= 3 * 10^4s[i]is'(', or')'.
Examples
Input: s = "(()"
Output: 2
Input: s = ")()())"
Output: 4
Input: s = ""
Output: 0
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Stack / Queue problems
- Asteroid CollisionMEDIUM
- Baseball GameEASY
- Basic CalculatorHARD
- Decode StringMEDIUM
- Evaluate Reverse Polish NotationMEDIUM
- Min StackMEDIUM
- Number of Recent CallsEASY
- Remove All Adjacent Duplicates In StringEASY
- Removing Stars From a StringMEDIUM
- Simplify PathMEDIUM
- Valid ParenthesesEASY