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 ')'.The goal is to find the length of the longest valid (well‑formed) parentheses substring within a given string. A common and efficient strategy uses a stack. The stack stores indices of characters, helping track unmatched parentheses. Whenever a valid pair is found, the stack helps determine the length of the current valid segment by comparing indices.
Another effective approach uses dynamic programming. Let dp[i] represent the length of the longest valid substring ending at index i. If the current character closes a valid pair, the DP state can extend the previous valid sequence. This allows the algorithm to accumulate lengths of nested or consecutive valid segments.
A third idea involves two linear scans (left-to-right and right-to-left) counting opening and closing parentheses. This helps detect balanced segments even when unmatched parentheses appear.
All major approaches run in O(n) time, with either stack memory or a DP array providing additional structure to track valid ranges.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based index tracking | O(n) | O(n) |
| Dynamic Programming | O(n) | O(n) |
| Two-pass counter scan | O(n) | O(1) |
NeetCode
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.
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.
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5int longestValidParentheses(const char *s)
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.
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.
Time Complexity: O(n), single pass through the string.
Space Complexity: O(n), array for DP results.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is frequently used in technical interviews at large tech companies. It tests knowledge of stacks, dynamic programming, and string processing, as well as the ability to reason about balanced structures.
A stack is one of the most commonly used data structures for this problem. It helps store indices of unmatched parentheses so that when a valid pair is found, the algorithm can quickly calculate the current valid substring length.
The optimal solutions run in O(n) time. Common approaches include using a stack to track indices of parentheses or using dynamic programming to store the longest valid substring ending at each index. Both approaches efficiently identify valid pairs and extend previously valid segments.
Yes, a two-pass scanning approach can solve the problem using O(1) extra space. By scanning left-to-right and right-to-left while counting opening and closing parentheses, the algorithm can detect balanced segments without using a stack or DP array.
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.