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.
This approach involves using a stack to keep track of indices of the opening parentheses. We iterate through the string and for each closing parenthesis, we pop from the stack to check if we have a matching opening parenthesis. By maintaining indices, we can calculate the length of valid substrings.
In this C implementation, the solution uses a stack to track indices of opening parentheses. A sentinel -1 is pushed initially to handle edge cases, such as the first valid substring extending to the start.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string. We traverse the string once.
Space Complexity: O(n), due to the stack that stores indices.
In this approach, we use a dynamic programming array where each entry at index i holds the length of the longest valid substring ending at that index. We iterate through the string, updating the DP array to keep track of valid pairs and their contributions to the overall length.
The C solution uses a DP array to accumulate the length of valid substrings. For each closing parenthesis, previous states are checked for forming valid pairs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), single pass through the string.
Space Complexity: O(n), array for DP results.
| Approach | Complexity |
|---|---|
| Using Stack | Time Complexity: O(n), where n is the length of the string. We traverse the string once. |
| Using Dynamic Programming | Time Complexity: O(n), single pass through the string. |
| 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 |
Valid Parenthesis String - Leetcode 678 - Python • NeetCode • 85,481 views views
Watch 9 more video solutions →Practice Longest Valid Parentheses with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor