32. Longest Valid Parentheses Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 * 10⁴
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.

Python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_length = 0

        for i, char in enumerate(s):
            if char == '(': 
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_length = max(max_length, i - stack[-1])

        return max_length

print(Solution().longestValidParentheses(")()())"))

Java

import java.util.Stack;

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxLength = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLength = Math.max(maxLength, i - stack.peek());
                }
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestValidParentheses(")()())"));
    }
}

C++

#include <iostream>
#include <stack>
#include <string>

int longestValidParentheses(const std::string &s) {
    std::stack<int> stack;
    stack.push(-1);
    int max_len = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.empty()) {
                stack.push(i);
            } else {
                max_len = std::max(max_len, i - stack.top());
            }
        }
    }
    return max_len;
}

int main() {
    std::string s = ")()())";
    std::cout << longestValidParentheses(s) << std::endl;
    return 0;
}

JavaScript

var longestValidParentheses = function(s) {
    const stack = [-1];
    let maxLen = 0;

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length === 0) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    return maxLen;
};

console.log(longestValidParentheses(")()())"));

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int longestValidParentheses(const char *s) {
    int max_len = 0, n = strlen(s);
    int *stack = (int *)malloc((n + 1) * sizeof(int));
    int top = -1;
    stack[++top] = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            stack[++top] = i;
        } else {
            if (top > -1) top--;
            if (top == -1) {
                stack[++top] = i;
            } else {
                int len = i - stack[top];
                if (len > max_len) max_len = len;
            }
        }
    }
    free(stack);
    return max_len;
}

int main() {
    char s[] = "()((()))";
    printf("%d", longestValidParentheses(s));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestValidParentheses(string s) {
        var stack = new Stack<int>();
        stack.Push(-1);
        int maxLen = 0;

        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i);
            } else {
                stack.Pop();
                if (stack.Count == 0) {
                    stack.Push(i);
                } else {
                    maxLen = Math.Max(maxLen, i - stack.Peek());
                }
            }
        }
        return maxLen;
    }

    static void Main(string[] args) {
        Console.WriteLine(new Solution().LongestValidParentheses(")()())"));
    }
}

This Python solution follows the stack-based approach akin to other programming languages, where indices are managed explicitly to compute valid substring lengths.

Complexity

Time Complexity: O(n).
Space Complexity: O(n).

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.

Python

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        maxLength = 0
        dp = [0] * len(s)

        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i - 1] == '(': 
                    dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
                elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(': 
                    dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
                maxLength = max(maxLength, dp[i])

        return maxLength

print(Solution().longestValidParentheses("()(()"))

Java

class Solution {
    public int longestValidParentheses(String s) {
        int maxLength = 0;
        int[] dp = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLength = Math.max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestValidParentheses("()(()"));
    }
}

C++

#include <iostream>
#include <vector>
#include <string>

int longestValidParentheses(const std::string& s) {
    std::vector<int> dp(s.length(), 0);
    int maxLength = 0;

    for (int i = 1; i < s.length(); ++i) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxLength = std::max(maxLength, dp[i]);
        }
    }

    return maxLength;
}

int main() {
    std::string s = ")(()())";
    std::cout << longestValidParentheses(s) << std::endl;
    return 0;
}

JavaScript

var longestValidParentheses = function(s) {
    let maxLength = 0;
    const dp = new Array(s.length).fill(0);

    for (let i = 1; i < s.length; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') { 
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
                dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
    }

    return maxLength;
};

console.log(longestValidParentheses("()(()"));

#include <stdio.h>
#include <string.h>

int longestValidParentheses(const char *s) {
    int maxLength = 0;
    int n = strlen(s);
    int dp[n];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxLength = (maxLength > dp[i]) ? maxLength : dp[i];
        }
    }
    return maxLength;
}

int main() {
    char s[] = "()(()";
    printf("%d", longestValidParentheses(s));
    return 0;
}

using System;

public class Solution {
    public int LongestValidParentheses(string s) {
        int maxLength = 0;
        int[] dp = new int[s.Length];

        for (int i = 1; i < s.Length; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLength = Math.Max(maxLength, dp[i]);
            }
        }
        return maxLength;
    }

    public static void Main(string[] args) {
        Console.WriteLine(new Solution().LongestValidParentheses("()(()"));
    }
}

In Python, we dynamically calculate longest valid length for closing parentheses using a DP list, allowing seamless accumulation of lengths.

Complexity

Time Complexity: O(n).
Space Complexity: O(n).

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.

TypeScript

function longestValidParentheses(s: string): number {
    const n = s.length;
    const f: number[] = new Array(n + 1).fill(0);
    for (let i = 2; i <= n; ++i) {
        if (s[i - 1] === ')') {
            if (s[i - 2] === '(') {
                f[i] = f[i - 2] + 2;
            } else {
                const j = i - f[i - 1] - 1;
                if (j && s[j - 1] === '(') {
                    f[i] = f[i - 1] + 2 + f[j - 1];
                }
            }
        }
    }
    return Math.max(...f);
}

func longestValidParentheses(s string) int {
	n := len(s)
	f := make([]int, n+1)
	for i := 2; i <= n; i++ {
		if s[i-1] == ')' {
			if s[i-2] == '(' {
				f[i] = f[i-2] + 2
			} else if j := i - f[i-1] - 1; j > 0 && s[j-1] == '(' {
				f[i] = f[i-1] + 2 + f[j-1]
			}
		}
	}
	return slices.Max(f)
}

Rust

impl Solution {
    pub fn longest_valid_parentheses(s: String) -> i32 {
        let mut ans = 0;
        let mut f = vec![0; s.len() + 1];
        for i in 2..=s.len() {
            if s.chars().nth(i - 1).unwrap() == ')' {
                if s.chars().nth(i - 2).unwrap() == '(' {
                    f[i] = f[i - 2] + 2;
                } else if (i as i32) - f[i - 1] - 1 > 0
                    && s.chars().nth(i - (f[i - 1] as usize) - 2).unwrap() == '('
                {
                    f[i] = f[i - 1] + 2 + f[i - (f[i - 1] as usize) - 2];
                }
                ans = ans.max(f[i]);
            }
        }
        ans
    }
}

Try this approach in the editor

Approach 4: Using Stack

Maintain a stack to store the indices of left parentheses. Initialize the bottom element of the stack with the value -1 to facilitate the calculation of the length of valid parentheses.
Iterate through each element of the string:
- If the character is a left parenthesis, push the index of the character onto the stack.
- If the character is a right parenthesis, pop an element from the stack to represent that we have found a valid pair of parentheses.
  - If the stack is empty, it means we couldn't find a left parenthesis to match the right parenthesis. In this case, push the index of the character as a new starting point.
  - If the stack is not empty, calculate the length of the valid parentheses and update it.

Summary:

The key to this algorithm is to maintain a stack to store the indices of left parentheses and then update the length of the valid substring of parentheses by pushing and popping elements.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.

TypeScript

function longestValidParentheses(s: string): number {
    let max_length: number = 0;
    const stack: number[] = [-1];
    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();

            if (stack.length === 0) {
                stack.push(i);
            } else {
                max_length = Math.max(max_length, i - stack[stack.length - 1]);
            }
        }
    }

    return max_length;
}

func longestValidParentheses(s string) int {
	ans := 0
	stack := []int{-1}
	for i, v := range s {
		if v == '(' {
			stack = append(stack, i)
		} else {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				stack = append(stack, i)
			} else {
				if ans < i-stack[len(stack)-1] {
					ans = i - stack[len(stack)-1]
				}
			}
		}
	}
	return ans
}

Rust

impl Solution {
    pub fn longest_valid_parentheses(s: String) -> i32 {
        let mut stack = vec![-1];
        let mut res = 0;
        for i in 0..s.len() {
            if let Some('(') = s.chars().nth(i) {
                stack.push(i as i32);
            } else {
                stack.pop().unwrap();
                if stack.is_empty() {
                    stack.push(i as i32);
                } else {
                    res = std::cmp::max(res, (i as i32) - stack.last().unwrap());
                }
            }
        }
        res
    }
}

PHP

class Solution {
    /**
     * @param string $s
     * @return integer
     */

    function longestValidParentheses($s) {
        $stack = [];
        $maxLength = 0;

        array_push($stack, -1);
        for ($i = 0; $i < strlen($s); $i++) {
            if ($s[$i] === '(') {
                array_push($stack, $i);
            } else {
                array_pop($stack);

                if (empty($stack)) {
                    array_push($stack, $i);
                } else {
                    $length = $i - end($stack);
                    $maxLength = max($maxLength, $length);
                }
            }
        }
        return $maxLength;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Stack	Time Complexity: O(n). Space Complexity: O(n).
Using Dynamic Programming	Time Complexity: O(n). Space Complexity: O(n).
Dynamic Programming	–
Using Stack	–

Complexity analysis

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

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.

Longest Valid Parentheses solution and explanation

The problem

Approach overview

Approach 1: Using Stack

Approach 2: Using Dynamic Programming

Approach 3: Dynamic Programming

Approach 4: Using Stack

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Valid Parentheses solution and explanation

The problem

Approach overview

Approach 1: Using Stack

Approach 2: Using Dynamic Programming

Approach 3: Dynamic Programming

Approach 4: Using Stack

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems