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: You receive a string containing only ( and ). The task is to compute the length of the longest contiguous substring that forms a valid parentheses sequence.
Approach 1: Brute Force Validation (O(n^3) time, O(1) space)
The simplest idea is to check every possible substring and verify whether it forms a valid parentheses sequence. Iterate over all start indices and end indices, extract the substring, and validate it using a counter or small stack. A substring is valid if parentheses are balanced and never go negative during the scan. This approach demonstrates the core property of balanced parentheses but becomes extremely slow because it evaluates O(n^2) substrings and each validation may take O(n) time.
Approach 2: Stack-Based Index Tracking (O(n) time, O(n) space)
This is the most common solution using a stack. Store indices of unmatched parentheses. Initialize the stack with -1 as a sentinel to represent the start of a potential valid substring. Iterate through the string: push the index for every (. For ), pop the stack. If the stack becomes empty, push the current index as a new base. Otherwise compute the current valid length as i - stack.top(). The stack stores boundaries of invalid segments, allowing you to measure valid ranges efficiently while scanning the string.
Approach 3: Dynamic Programming (O(n) time, O(n) space)
The dynamic programming solution tracks the length of the longest valid substring ending at each index. Create an array dp[i] where dp[i] represents the longest valid parentheses substring ending at position i. When encountering ), two patterns may form: a direct pair () or a nested/extended structure like ...)). For the first case, set dp[i] = dp[i-2] + 2. For the second, check the character before the previous valid block and extend it if it forms a matching (. This approach uses dynamic programming to reuse previously computed valid segments and build longer ones.
Recommended for interviews: The stack solution is the most expected answer in interviews because it demonstrates clear reasoning about boundaries and invalid segments while maintaining O(n) time complexity. Dynamic programming is equally optimal and shows stronger algorithmic thinking, especially when explaining how valid substrings combine. Brute force rarely appears as a final solution but helps explain the constraints and why linear-time strategies are required.
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
C++
Java
Python
C#
JavaScript
Go
TypeScript
Rust
PHP
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.
Time Complexity: O(n), single pass through the string.
Space Complexity: O(n), array for DP results.
We define f[i] to be the length of the longest valid parentheses that ends with s[i-1], and the answer is max(f[i]).
When i \lt 2, the length of the string is less than 2, and there is no valid parentheses, so f[i] = 0.
When i \ge 2, we consider the length of the longest valid parentheses that ends with s[i-1], that is, f[i]:
s[i-1] is a left parenthesis, then the length of the longest valid parentheses that ends with s[i-1] must be 0, so f[i] = 0.s[i-1] is a right parenthesis, there are the following two cases:s[i-2] is a left parenthesis, then the length of the longest valid parentheses that ends with s[i-1] is f[i-2] + 2.s[i-2] is a right parenthesis, then the length of the longest valid parentheses that ends with s[i-1] is f[i-1] + 2, but we also need to consider whether s[i-f[i-1]-2] is a left parenthesis. If it is a left parenthesis, then the length of the longest valid parentheses that ends with s[i-1] is f[i-1] + 2 + f[i-f[i-1]-2].Therefore, we can get the state transition equation:
$
\begin{cases}
f[i] = 0, & if s[i-1] = '(',\
f[i] = f[i-2] + 2, & if s[i-1] = ')' and s[i-2] = '(',\
f[i] = f[i-1] + 2 + f[i-f[i-1]-2], & if s[i-1] = ')' and s[i-2] = ')' and s[i-f[i-1]-2] = '(',\
\end{cases}
Finally, we only need to return max(f).
The time complexity is O(n), and the space complexity is O(n), where n$ is the length of the string.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Validation | O(n^3) | O(1) | Conceptual understanding of valid parentheses before optimizing |
| Stack-Based Index Tracking | O(n) | O(n) | General case; most common interview solution |
| Dynamic Programming | O(n) | O(n) | When you want to explicitly track valid substring lengths ending at each index |
Longest Valid Parentheses | Live Coding with Explanation | Leetcode - 32 • Algorithms Made Easy • 62,858 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