32. Longest Valid Parentheses
You are given a string s consisting only of the characters ( and ) (it may be empty). Return the length of the longest contiguous substring of s that forms a well-formed parentheses sequence — one where every ( is matched by a later ) and no prefix ever has more closers than openers.
If s contains no non-empty valid substring at all, the answer is 0.
The answer is a single integer, and since valid sequences pair brackets up, it is always even.
Example 1:
Input: s = "(()"
Output: 2
Explanation: The whole string never balances, but its suffix "()" does, giving length 2.
Example 2:
Input: s = ")()())"
Output: 4
Explanation: The middle stretch "()()" is well-formed and no longer valid stretch exists.
Constraints:
- 0 ≤ s.length ≤ 3 * 10⁴
- s[i] is '(' or ')'
Hints:
A substring is well-formed exactly when its running balance (opens minus closes, scanned left to right) never dips below zero and finishes at zero.
Keep a stack of indices with a sentinel below everything. Push each '(' index; on ')' pop — if the stack still has something, the run ending here has length i minus the new top; if it emptied, this ')' becomes the new barrier.
For the DP view: let dp[i] be the longest valid run ending exactly at i. A ')' either closes the '(' right before it, or jumps over the dp[i-1] block to look for its partner.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "(()"
Expected output: 2