#32 Longest Valid Parentheses
the problem
In plain words
You get a string made only of '(' and ')'. Find the longest contiguous piece of it that is a well-formed parentheses string, and return that length.
in s = "(()"
out 2
The valid piece is "()".
in s = ")()())"
out 4
The valid piece is "()()".
in s = ""
out 0
- 0 ≤ s.length ≤ 3·10⁴
- s[i] is '(' or ')'
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternStack for matching & nesting1D DP
A valid run is broken only by a ')' with no partner, or by a '(' that never gets one. Keep the index just before the current run at the bottom of a stack of indices: when a ')' at i finds its partner, the run that ends at i is i − (index on top).
solutions
From brute force to optimal
From each start i, walk right counting open brackets. Balance 0 means s[i..j] is valid; a negative balance means nothing starting at i can pass j.
- For each i: balance = 0.
- For j = i..n−1: '(' → +1, ')' → −1.
- balance < 0 → stop this start; balance == 0 → best = max(best, j − i + 1).
Up to n(n + 1)/2 (start, end) pairs — about 4.5·10⁸ at n = 3·10⁴.
Two counters.
class Solution { public int longestValidParentheses(String s) { int best = 0; for (int i = 0; i < s.length(); i++) { // every start int balance = 0; // open '(' not yet closed for (int j = i; j < s.length(); j++) { balance += s.charAt(j) == '(' ? 1 : -1; if (balance < 0) break; // a ')' with no partner: no valid run passes j if (balance == 0) best = Math.max(best, j - i + 1); // s[i..j] is balanced } } return best; }}Push −1 as a base. '(' pushes its index. ')' pops: if the stack becomes empty, this ')' is the new base; otherwise the run ending here is i − top.
- stack = [−1], best = 0.
- '(' → push i.
- ')' → pop. Empty now? push i (new base). Otherwise best = max(best, i − peek()).
- Return best.
One pass; each index is pushed once and popped at most once.
A string of only '(' keeps every index on the stack.
class Solution { public int longestValidParentheses(String s) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(-1); // base: the index just before the current valid run int best = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); // wait for a partner } else { stack.pop(); // match the top '(' (or throw away the old base) if (stack.isEmpty()) { stack.push(i); // an unmatched ')' becomes the new base } else { best = Math.max(best, i - stack.peek()); // valid run = everything after the top } } } return best; }}Dry run
Left to right, count '(' and ')': equal → a valid run; more ')' → reset. A run like "(()" never balances that way, so repeat right to left with the roles swapped.
- Left → right: open/close counters; equal → best = max(best, 2 × close); close > open → reset both.
- Right → left: same, but reset when open > close.
Two passes over the string.
Two counters — no stack.
class Solution { public int longestValidParentheses(String s) { int best = 0, open = 0, close = 0; for (int i = 0; i < s.length(); i++) { // left → right if (s.charAt(i) == '(') open++; else close++; if (open == close) best = Math.max(best, 2 * close); else if (close > open) open = close = 0; // too many ')': nothing extends past here } open = close = 0; for (int i = s.length() - 1; i >= 0; i--) { // right → left catches runs like "(()" if (s.charAt(i) == '(') open++; else close++; if (open == close) best = Math.max(best, 2 * open); else if (open > close) open = close = 0; } return best; }}in the room
How to say it in the interview
talk track
- Start from Valid Parentheses: the stack tells me which ')' have partners. The new question is how long each matched run is.
- Explain the base: the bottom of the stack is always the index just before the current run, so the length is i − top.
- Walk through ")()())": the first ')' becomes the base, then runs of 2 and 4 are measured.
- Offer the two-counter version if asked for O(1) space.
traps
- Counting matched pairs instead of measuring runs: "()(()" has two pairs, but the longest valid run is 2, not 4.
- Forgetting the −1 base — the first measurement then needs a special case.
- One left-to-right counter pass alone misses runs like "(()" — you need the right-to-left pass too.
what they ask next
Follow-ups
Can you solve it with DP?
dp[i] = length of the longest valid run ending at i. For s[i] == ')': if s[i−1] == '(' then dp[i] = dp[i−2] + 2; else if the char before the run ending at i − 1 is '(' then dp[i] = dp[i−1] + 2 + the run before that. O(n) time and space.
before you submit
Edge cases to test
- Empty string → 0.
- ")(" → 0: nothing pairs up.
- "()(()" → 2: the extra '(' at index 2 keeps the two runs apart.
- "()(())" → 6: runs that touch join into one.
practise next
Similar problems
- #20Valid ParenthesesEasyin Stacks
- #22Generate ParenthesesMediumin Backtracking
- #84Largest Rectangle in HistogramHardin Stacks