DSA problem
Longest Valid Parentheses
Given a string s containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
The substring must be contiguous in s, and "valid" means a properly nested and matched sequence of parentheses (the same definition used by the standard Valid Parentheses problem, except over ( and ) only).
A brute-force solution checks every substring for validity, which is O(n^3). A dynamic-programming approach exists in O(n) time and O(n) space but requires careful case analysis on whether s[i] is ')' and what s[i - dp[i - 1] - 1] is.
The cleanest O(n) solution uses a stack of INDICES, seeded with -1 as a base. This sentinel represents the position just before any valid substring could start. Walk s from left to right: on '(' push the index. On ')', pop the top: if the stack is now empty, the popped index was the new "base" — push the current index as the new base. Otherwise, the current valid substring spans from the new top of the stack (exclusive) to the current index (inclusive), which has length i - stack.top(). Track the maximum such length across the scan. This is O(n) time and O(n) space.
Examples
s = "(()"2s = ")()())"4s = ""0Constraints
- 0 <= s.length <= 3 * 10^4
- s[i] is '(', or ')'.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.