hardStack / QueuePure DSA~40 min
Longest Balanced Log Segment
A trace log encodes nested spans as '(' (span open) and ')' (span close). Some spans are malformed. Find the length of the longest contiguous run that is perfectly balanced.
Problem
Given a string containing only '(' and ')', return the length of the longest substring that is a well-formed (valid) parentheses sequence.
Input
A string s (0 ≤ |s| ≤ 3·10^4) of '(' and ')'.
Output
An integer: the length of the longest valid parentheses substring.
Constraints
- 0 ≤ |s| ≤ 3·10^4
- Only '(' and ')' characters
- Substring must be contiguous and fully balanced
Examples
Example 1
Input
s = "(()"
Output
2
The substring '()' at the end is the longest valid run.
Example 2
Input
s = ")()())"
Output
4
'()()' in the middle has length 4.