Watch 10 video solutions for Longest Valid Parentheses, a hard level problem involving String, Dynamic Programming, Stack. This walkthrough by NeetCode has 85,481 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()".
Example 2:
Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()".
Example 3:
Input: s = "" Output: 0
Constraints:
0 <= s.length <= 3 * 104s[i] is '(', or ')'.Problem Overview: Given a string containing only '(' and ')', return the length of the longest substring that forms a valid (well‑formed) parentheses sequence. The substring must be continuous and properly balanced.
Approach 1: Brute Force Validation (O(n^3) time, O(1) space)
Check every possible substring and verify if it forms a valid parentheses sequence. For each start index i, iterate to every end index j, then run a validation pass that counts opening and closing brackets. A substring is valid if the balance never goes negative and ends at zero. This approach is straightforward but inefficient because it generates O(n^2) substrings and each validation takes O(n). Useful only for understanding the definition of a valid sequence.
Approach 2: Stack (O(n) time, O(n) space)
The stack approach tracks indices of unmatched parentheses. Push indices of '(' onto the stack. When encountering ')', pop the stack to match a previous '('. If the stack becomes empty, push the current index as a new base. Otherwise, compute the current valid length using i - stack.top(). The key insight: storing indices lets you measure the length of the latest valid window after every match. This method is widely used in interviews and demonstrates strong understanding of stack operations on string problems.
Approach 3: Dynamic Programming (O(n) time, O(n) space)
Create a DP array where dp[i] stores the length of the longest valid substring ending at index i. When you see ')', check if it forms a pair with the previous character or connects to an earlier valid block. Two transitions handle cases like "()" and nested patterns such as "(())". Specifically, if s[i] == ')' and s[i-1] == '(', then dp[i] = dp[i-2] + 2. Otherwise check if a previous valid block allows matching another '('. This approach highlights pattern building typical in dynamic programming string problems.
Recommended for interviews: The stack solution is the most commonly expected answer because it is intuitive and linear time. The dynamic programming approach also runs in O(n) and demonstrates deeper algorithmic reasoning. Mentioning the brute force approach first shows you understand the problem space, but implementing the stack or DP method proves strong optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Check | O(n^3) | O(1) | Conceptual baseline to understand valid parentheses validation |
| Stack with Index Tracking | O(n) | O(n) | Most common interview solution; simple and intuitive |
| Dynamic Programming | O(n) | O(n) | Useful when reasoning about substring patterns and extending previous valid states |