Longest Valid Parentheses
Problem statement
You get a string s made only of ( and ). Return the length of the longest contiguous substring that is a well-formed sequence of parentheses, meaning every ( is closed by a later ) and no ) appears before its matching (.
Return 0 if there is none, including for the empty string. Note that the answer is about a substring, not about fixing the whole string.
Examples
Example 1
Input: s = "(()())("
Output: 6
Explanation: The first six characters, "(()())", are balanced; the last "(" never closes.
Example 2
Input: s = "())(())"
Output: 4
Explanation: The stray ")" at index 2 splits the string. "()" before it has length 2 and "(())" after it has length 4.
Hints
Approach
Two counting passes. Scan left to right with counters open and close. When they are equal, the stretch since the last reset is balanced, so record 2 · close. When close > open, a ) has no partner: reset both to 0.
That pass misses runs with extra ( that never close, such as ((), because open stays ahead. So scan again from right to left with the roles swapped: record on equality and reset when open > close. The best from both passes is the answer.
O(n)Space O(1)def longest_valid_parentheses(s): best = 0 opens = closes = 0 for ch in s: if ch == "(": opens += 1 else: closes += 1 if opens == closes: best = max(best, 2 * closes) elif closes > opens: opens = closes = 0 opens = closes = 0 for ch in reversed(s): if ch == "(": opens += 1 else: closes += 1 if opens == closes: best = max(best, 2 * opens) elif opens > closes: opens = closes = 0 return best print(longest_valid_parentheses("(()())("))print(longest_valid_parentheses("())(())"))Follow-up questions
- Return the substring itself, not just its length.
- Allow three bracket types,
(),[]and{}. Which approach still works? (The stack of indices, checking types when popping.)
Frequently asked questions
Bracket matching underlies parsing config formats, templating languages and expressions in alerting rules. The hard version is a common SWE-loop question because it has three genuinely different solutions (stack, DP, two counters), and interviewers like to see you move from one to the next.
A valid run that begins at index 0 needs a boundary to its left so its length can be computed as i - stack[-1]. The sentinel -1 plays that role until an unmatched ) replaces it.
Yes. Let dp[i] be the length of the longest valid run ending at i. For ) preceded by (, dp[i] = dp[i-2] + 2. For ) preceded by ), look at the character before the run ending at i - 1; if it is (, then dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]. It is O(n) time and space, like the stack.