Longest Valid Parentheses
Hard · Stack & Strings · String · Stack · Dynamic Programming
Problem
Given a string s made only of ( and ), return the length of the longest contiguous substring that is a well-formed parentheses string — every ( closed by a later ), and no ) without an earlier ( to close.
Return 0 if there is no such substring (including when s is empty).
Examples
Input: s = "(()" Output: 2
The longest valid substring is (). The first ( is never closed.
Input: s = ")()())" Output: 4
The longest valid substring is ()().
Input: s = "" Output: 0
Constraints
- 0 <= len(s) <= 3 * 10^4
- s[i] is '(' or ')'
Approaches
- Stack of indices with a wall at the bottom — time O(n), space O(n)
Follow-up
Can you solve it in O(1) extra space? Hint: scan left to right with two counters, then right to left.
Related problems
Start free on Cariara · Coding problems · System design studio
