Longest Valid Parentheses
Given a string s containing only ( and ), return the length of the longest valid (well-formed) parentheses substring.
Intuition
A stack of indices — not characters — tracks unmatched parentheses. Push the index of every (. When you see ), pop: if the stack is not empty, the distance from the current index to the new top is the length of the valid substring ending here. The clever part is what you push before starting: seed the stack with -1 as a base index. This way, when a ) matches the only remaining (, the length computation still works — i - (-1) gives the correct count. Without this sentinel, the first valid pair would need special-casing.
When a problem asks for the longest valid parentheses substring, the shape is a stack of indices rather than characters. The sentinel (initial -1) is the key trick — it marks where the previous invalid character was, so the length of the current valid run is always i - stack.top(). This index-stack technique extends to any balanced-bracket problem where you need lengths, not just validity.
Approach
Seed the stack with -1 as a boundary marker
Push -1 onto the stack before scanning. This acts as the 'last unmatched index before the current valid run'. It ensures that the length formula i - stack[-1] works even for valid substrings starting at index 0.
Push indices of `(` and handle `)` with pop-then-measure
For each (, push its index. For each ), pop the top. If the stack is now empty, the ) is unmatched — push its index as the new boundary marker. If the stack is not empty, the valid substring ending at i has length i - stack[-1]. Update max_len accordingly.
The answer is the maximum length seen across all positions
After scanning the entire string, max_len holds the answer. Time is O(n) — each index is pushed and popped at most once. Space is O(n) for the stack.
Solution
Common pitfalls
Forgetting to seed the stack with -1
stack = []
stack = [-1]
Without the sentinel, a valid substring starting at index 0 (like ()) has no base to subtract from. i - stack[-1] would use a stale index or crash on an empty stack.
Pushing the current index as a new boundary only when the stack is truly empty
if ch == ')':
stack.pop()
max_len = max(max_len, i - stack[-1])if ch == ')':
stack.pop()
if not stack:
stack.append(i)
else:
max_len = max(max_len, i - stack[-1])If the pop empties the stack, stack[-1] is an index error. The unmatched ) must become the new boundary by pushing its index.
Computing length as i - stack[-1] + 1 instead of i - stack[-1]
max_len = max(max_len, i - stack[-1] + 1)
max_len = max(max_len, i - stack[-1])
The stack top is the index before the valid run starts, not the start of the run. The length from position stack[-1] + 1 to i (inclusive) is i - stack[-1], not i - stack[-1] + 1. Adding 1 overcounts by one.
Edge cases
(((No ) ever pops, so no length is computed. max_len stays 0.
)))Each ) finds the stack either containing only the sentinel (which it replaces) or empty after popping the sentinel. No valid substring.
()()The sentinel -1 stays at the bottom. After the last ), the length is 3 - (-1) = 4. Correct.
)()()The first ) replaces the sentinel with index 0. Then ()() from index 1 to 4 gives length 4 - 0 = 4.