HardStringDynamic ProgrammingStackBracket SequencesUpdated Sep 2026

32. Longest Valid Parentheses

Asked at Meta, Visa

Difficulty

Hard

Time

O(n)

Space

O(n)

Pattern

String

Companies

2

Problem

You are given a string s made only of the characters ( and ). Your job is to find the length of the longest valid parentheses substring.

A substring is a block of characters that sit next to each other in s. A substring is valid when every ( has a matching ) after it, and the pairs are properly nested. For example, "()" and "()()" are valid, but ")(" and "(()" are not.

Return a single integer: the length of the longest valid substring. If no valid substring exists, return 0.

Find the longest valid block

svalid, length 2(()012The pair at indices 1 and 2 is valid; the first '('has no partner.
Only unbroken stretches of matched parentheses count. In "(()" the best block is "()" with length 2.

Constraints

  • ●0 <= s.length <= 3 * 10^4
  • ●s[i] is '(' or ')'

Examples

Example 1
Inputs = "(()"
Output2
WhyThe only valid block is the pair "()" at positions 1 and 2, which has length 2. The leading "(" is left unmatched.
Example 2
Inputs = ")()())"
Output4
WhyThe middle part "()()" is valid and has length 4. The first ")" and the last ")" cannot be matched, so they are not included.
Example 3
Inputs = ""
Output0
WhyAn empty string has no characters, so there is no valid substring and the answer is 0.

Asked At

2 companies
CompanyDifficulty
MetaHardView all Meta questions →
VisaHardView all Visa questions →

How to Think About It

1

A brute force approach checks every possible substring and validates whether it is a well-formed parentheses string.

2

This is O(n^3) which is too slow for large inputs.

3

A stack-based approach can track indices of unmatched parentheses and compute valid lengths between them.

4

Use a stack initialized with -1 as a base index. Push index of open paren, pop on close paren and update max length.

5

A DP approach where dp[i] stores the length of the longest valid substring ending at index i can also work in O(n).

Optimal Approach

Use a stack initialized with -1 as a sentinel base index. Iterate through the string: push the index of each open parenthesis. For each close parenthesis, pop from the stack. If the stack is empty after popping, push the current index as the new base. Otherwise, update the maximum length as the difference between the current index and the new stack top. This computes the longest valid substring in O(n) time and O(n) space.

Stack of unmatched indices

stack-1← topStart with -1 as a base index, so a valid blockstarting at index 0 has length i - (-1).stack-101← topPush the index of every '(' we see. After reading"((", the stack is [-1, 0, 1].stack-10← topAt index 2 we see ')', so we pop index 1. The stack isnot empty, so length = 2 - 0 = 2.')' → pop the stackempty after pop → push i as new baseelse → best = max(best, i - stack[-1])
The stack always holds the indices of unmatched characters. The gap from the top of the stack to the current index is a valid length.
ComplexityTime O(n)Space O(n)We scan the string once, and the stack can hold up to n indices in the worst case.

What Trips People Up in Real Interviews

1

Clarify what constitutes a valid parentheses substring — each open must have a matching close in the correct order.

2

The stack approach is the most intuitive and commonly expected in interviews.

3

Walk through examples to show how the stack stores indices and computes lengths.

4

Discuss the two-pointer alternative which achieves O(1) space but is trickier to implement.

5

Edge cases: all open parens, all close parens, empty string, alternating invalid pattern like ")(".

Solution Code

O(n) time
def longestValidParentheses(s):
    stack = [-1]
    max_len = 0
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Longest Valid Parentheses problem?

Given a string containing just the characters open and close parentheses, find the length of the longest valid (well-formed) parentheses substring.

How do you solve Longest Valid Parentheses?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Longest Valid Parentheses?

Longest Valid Parentheses is asked at Meta, Visa. It is a hard difficulty problem.

What are common mistakes on Longest Valid Parentheses?
  • Clarify what constitutes a valid parentheses substring — each open must have a matching close in the correct order.
  • The stack approach is the most intuitive and commonly expected in interviews.
  • Walk through examples to show how the stack stores indices and computes lengths.
  • Discuss the two-pointer alternative which achieves O(1) space but is trickier to implement.
  • Edge cases: all open parens, all close parens, empty string, alternating invalid pattern like ")(".