Longest Valid Parentheses

HardStack · Two-Pass Counting🧩 Stack LeetCode #32 ↗Updated Oct 30, 2026

Problem

A string s contains only '(' and ')'. Return the length of the longest contiguous substring that is a well-formed (balanced and properly nested) parentheses sequence. Return 0 if none exists.

Input")()())"Output4 ("()()")

Input"(()"Output2

Input""Output0

0 ≤ s.length ≤ 3·10⁴ · s[i] is '(' or ')'

Try it yourself

Java

class Solution {
    public int longestValidParentheses(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

An unmatched ')' acts as a wall: no valid substring can cross it. Track the last wall (stack of indices) — or just count opens/closes and reset at each wall.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForceCheck Every Even-Length Substring

Time O(n³)Space O(1)

For every start i and every even end j, scan s[i..j) with a balance counter: it must never go negative and must end at 0. Keep the longest valid length.

Java

public int longestValidParentheses(String s) {
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 2; j <= s.length(); j += 2) {   // even lengths only
            if (isValid(s, i, j)) maxLen = Math.max(maxLen, j - i);
        }
    }
    return maxLen;
}

private boolean isValid(String s, int from, int to) {
    int balance = 0;
    for (int k = from; k < to; k++) {
        balance += s.charAt(k) == '(' ? 1 : -1;
        if (balance < 0) return false;                  // more ')' than '('
    }
    return balance == 0;
}

Obviously correct, but cubic — hopeless at n = 3·10⁴.

BetterStack of Indices

Time O(n)Space O(n)

Push indices of '('. The stack bottom holds the index of the last unmatched ')' (start with -1). On ')', pop; if the stack becomes empty this ')' is the new wall, else the valid run ending here is i - stack.peek().

Java

public int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);                    // wall before the string
    int maxLen = 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);           // unmatched ')' = new wall
            else maxLen = Math.max(maxLen, i - stack.peek());
        }
    }
    return maxLen;
}

Linear time, single pass; O(n) stack in the worst case (all '(').

OptimalTwo-Pass Open/Close Counters

Time O(n)Space O(1)

Left→right, count open/close: equal counts mean a valid run of 2·close; close > open is a wall, so reset. This misses runs with surplus '(' like "(()", so repeat right→left with the roles swapped.

Java

public int longestValidParentheses(String s) {
    int open = 0, close = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') open++; else close++;
        if (open == close) maxLen = Math.max(maxLen, 2 * close);
        else if (close > open) open = close = 0;        // wall: reset
    }
    open = close = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') open++; else close++;
        if (open == close) maxLen = Math.max(maxLen, 2 * open);
        else if (open > close) open = close = 0;
    }
    return maxLen;
}

Dry run")()())"

i index changed

i=0
)
i
(

)

(

)

)

c>o → reset, max=0
i=1
)

(
i
)

(

)

)

o=1 c=0
i=2
)

(

)
i
(

)

)

o=1 c=1 → max=2
i=3
)

(

)

(
i
)

)

o=2 c=1
i=4
)

(

)

(

)
i
)

o=2 c=2 → max=4
i=5
)

(

)

(

)

)
i
c>o → reset; answer 4 ✔

Linear time and constant memory — best possible.

Pro tip

A DP alternative: dp[i] = longest valid run ending at i, also O(n) time but O(n) space.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Even-Length Substring	`O(n³)`	`O(1)`
Better	Stack of Indices	`O(n)`	`O(n)`
Optimal	Two-Pass Open/Close Counters	`O(n)`	`O(1)`

Common pitfalls

Counting only total balance — ")(" is balanced but not valid.
Doing only the left→right pass — "(()" returns 0 instead of 2.
Forgetting the -1 sentinel — runs starting at index 0 are mis-measured.

Interview tips

Clarify: substring (contiguous), not subsequence.
Explain the stack bottom as “index just before the current valid run”.
Show the "(()" counter-example to justify the second pass.

Pattern

Stack of indices / balance counters → longest contiguous well-formed bracket segment.

My notes saved in this browser