Skip to main content
Talentd

Longest Valid Parentheses - Solution & Explanation

HardStringDynamic ProgrammingStack30 min readAsked at: Amazon, Microsoft, Meta +22
Practice this problem

Problem Statement

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 * 104
  • s[i] is '(', or ')'.

Approach Overview

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.

Approach 1: Using Stack

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.

Code

CC++JavaPythonC#JavaScriptGoTypeScriptRustPHP

C

C++

Java

Python

C#

JavaScript

Go

TypeScript

Rust

PHP

Complexity

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.

Try this approach in the editor →

Approach 2: Using Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), single pass through the string.
Space Complexity: O(n), array for DP results.

Try this approach in the editor →

Approach 3: Dynamic Programming

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]:

  • If 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.
  • If s[i-1] is a right parenthesis, there are the following two cases:
    • If 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.
    • If 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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Stack

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.

Using Dynamic Programming

Time Complexity: O(n), single pass through the string.
Space Complexity: O(n), array for DP results.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ValidationO(n^3)O(1)Conceptual understanding of valid parentheses before optimizing
Stack-Based Index TrackingO(n)O(n)General case; most common interview solution
Dynamic ProgrammingO(n)O(n)When you want to explicitly track valid substring lengths ending at each index

Video Solution

Longest Valid Parentheses | Live Coding with Explanation | Leetcode - 32 • Algorithms Made Easy • 64,901 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Valid Parentheses easy or hard?
Longest Valid Parentheses is classified as a Hard problem on LeetCode. The challenge comes from correctly handling nested and overlapping parentheses while maintaining linear time complexity. Mastery usually requires familiarity with stack-based parsing or dynamic programming patterns.
Longest Valid Parentheses Python/Java solution
Python and Java implementations typically use a stack storing indices with an initial value of -1. Each time a closing parenthesis is processed, the stack is popped and the current valid length is calculated using the difference between the current index and the new stack top. This produces an O(n) solution.
How to solve Longest Valid Parentheses in O(n)?
Use either a stack or dynamic programming. The stack method stores indices of unmatched parentheses and calculates valid substring lengths using index differences as you scan the string. The dynamic programming method keeps a dp array where dp[i] represents the longest valid substring ending at index i.
What is the best approach for Longest Valid Parentheses?
The stack-based approach is widely considered the best interview solution. It scans the string once while storing indices of unmatched parentheses and computing valid lengths using index differences. This achieves O(n) time complexity with O(n) space and is easy to reason about during interviews.
Is Longest Valid Parentheses asked at Google/Amazon/Meta?
Longest Valid Parentheses appears in interview preparation lists for companies such as Google, Amazon, and Meta because it tests stack usage, string parsing, and dynamic programming reasoning. Variations of parentheses validation and longest valid substring problems are common in technical interviews.
What data structure is used in Longest Valid Parentheses?
The most common data structure used is a stack that stores indices of parentheses. It helps track boundaries of unmatched characters and calculate valid substring lengths efficiently. Dynamic programming is another technique used to build valid substring lengths incrementally.
What is the time complexity of Longest Valid Parentheses?
The optimal algorithms run in O(n) time where n is the length of the string. Both the stack approach and the dynamic programming solution process each character once. Brute force solutions are much slower at O(n^3) because they evaluate every substring.

Ready to solve this problem?

Practice Longest Valid Parentheses with our built-in code editor and test cases.

Practice on FleetCode
Previous

Valid Parentheses