Problem statement

Given a string s of '(' and ')', return the length of the longest valid (well-formed and contiguous) parentheses substring.

Example 1

Input: s = "(()"
Output: 2
Explanation: The longest valid substring is "()".

Example 2

Input: s = ")()())"
Output: 4

Example 3

Input: s = ""
Output: 0

Constraints

• 0 <= s.length <= 40
• s consists of '(' and ')'.

Hints for Longest Valid Parentheses

1. Hint 1

   Keep a stack of indices, seeded with -1 to mark the base of the current valid run.

2. Hint 2

   Push the index of every (; on a ), pop.

3. Hint 3

   If the stack empties, this ) is unmatched — push its index as the new base; otherwise the run length is the current index minus the new top.

How to solve Longest Valid Parentheses

Keep a stack of indices seeded with -1 as the base of the current valid run; push ( indices, pop on ), and either record i - newTop or, if the stack empties, push i as the new base.

Approach

1. Start stack = [-1].
2. On (, push i; on ), pop; if empty, push i; else best = max(best, i - stack[-1]).
3. Return best.

Why it works

The top of the stack after a successful pop is the index just before the current valid run began, so i - top is its length. An unmatched ) resets the base because nothing valid can span it.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The two-counter O(1) approach scans both directions to handle (() and ()) symmetrically.

Reference solution

Python

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Java

public static int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    int best = 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 {
                best = Math.max(best, i - stack.peek());
            }
        }
    }
    return best;
}

C++

int longestValidParentheses(string s) {
    vector<int> stack;
    stack.push_back(-1);
    int best = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] == '(') {
            stack.push_back(i);
        } else {
            stack.pop_back();
            if (stack.empty()) {
                stack.push_back(i);
            } else {
                best = max(best, i - stack.back());
            }
        }
    }
    return best;
}

JavaScript

var longestValidParentheses = function(s) {
    const stack = [-1];
    let best = 0;
    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 {
                const len = i - stack[stack.length - 1];
                if (len > best) best = len;
            }
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard