{ }SolveLogs
⌕
Home / Stack / #32
LeetCode #32 Hard

Longest Valid Parentheses

Longest Valid Parentheses is LeetCode 32 (Hard). The string s contains only ( and ). Return the length of the longest substring that is well-formed: every ( in it is closed by a later ) in it, and no ) appears before its partner.

  • The answer is a length, not the substring itself, and it is 0 when no two brackets pair up.
  • It must be contiguous. Pairs scattered across the string do not add up unless the stretch between them is balanced too.
  • s can be empty and has at most 3 × 10⁴ characters, so checking every substring (O(n³), or O(n²) with care) is too slow; the target is one O(n) pass.
Constraints
  • 0 <= s.length <= 3 * 10⁴
  • s[i] is '(', or ')'.
stackdynamic-programmingstrings
Open on LeetCode ↗
02

Intuition

Checking a whole string is the stack problem from Valid Parentheses. Here the question is where the balanced stretches are, and the brackets that never match decide that. An unmatched ) or ( is a wall: no valid substring can contain it, so the answer is the longest gap between two walls.

That is why the stack stores indices, with the most recent wall kept under the open brackets of the current run. When a ) closes a pair, the length of the run ending there is just i minus the index now on top. Measuring from the wall rather than from the matching ( is what joins neighbouring runs: in ()() the second ) reaches back to the start and gets 4, not 2.

How to spot this pattern

"Longest contiguous stretch that satisfies a balance rule" usually means tracking where the stretch is forced to break. The longest valid parentheses LeetCode problem is the clearest case: the breaks are unmatched indices, and a stack of indices finds them on the fly. Whenever you need the length of a balanced region rather than a yes/no, store positions on the stack, not characters.

03

Approach

Try it first

Before reading on, run a stack of indices by hand on ")()())" and write down the top of the stack after every character. Which index should a run ending at position 4 subtract? Aim for O(n) time.

Two ways to solve it

Index stackBest
Time O(n)Space O(n)

Keep the indices of unmatched brackets on a stack seeded with -1, and measure each run as i - top.

  • Logic: one push or pop per character.
  • Edge cases: the -1 seed covers them.
  • Explains: why runs break where they do.

The easiest to get right under pressure.

Solution & demo ↓
Dynamic programming
Time O(n)Space O(n)

Store dp[i], the longest valid run ending at i, and build each ) from the run before it.

  • Logic: two cases, with index arithmetic.
  • Edge cases: bounds checks on i - 2 and j - 1.
  • Explains: how adjacent runs join.

Same cost, more places to slip.

Code ↓

Both run in O(n) time and space, but the stack has one rule per character where the DP has two cases full of index offsets. The steps, code and live demo below follow the stack; the DP code comes after the demo.

1

Seed the base

Start with stack = [-1] and best = 0. The -1 is an imaginary wall just before index 0, so a run that begins at the very start can still be measured as i - (-1) = i + 1 without a special case.

2

Push every opening bracket's index

On (, push i. While it waits for a partner, nothing to its left can join a run that ends to its right, so it acts as a wall until a ) pops it. If it never closes, it simply stays on the stack.

3

Pop on a closing bracket, then branch

On ), pop once, then:

  • Stack empty: the pop removed the wall, not an open bracket, so this ) is unmatched. Push i as the new wall.
  • Stack not empty: a pair just closed, and the top is the last wall, so update best = max(best, i - stack[-1]).
4

Why measuring from the wall is correct

After each index, the bottom of the stack is the last unmatched ) (or -1) and the rest are the ( still open since then. Everything between the top and i is therefore balanced, and every maximal valid run ends at a ) that measures all of it.

04

Longest Valid Parentheses solution in Python | C++ | Java

▶1class Solution:
▶2 def longestValidParentheses(self, s: str) -> int:
▶3 stack = [-1]
▶4 best = 0
▶5 for i, ch in enumerate(s):
▶6 if ch == "(":
▶7 stack.append(i)
▶8 else:
▶9 stack.pop()
▶10 if not stack:
▶11 stack.append(i)
▶12 else:
▶13 best = max(best, i - stack[-1])
▶14 return best
)0(1)2(3)4)5wall -1best 0stack-1topseed the stack with the base -1
stack[-1]-1 = wall before index 0
best0
Idea. The stack holds indices, and its top is always the wall just before the current valid run, so a run ending at i has length i − top. Seeding -1 gives a run that starts at index 0 something to subtract.
)0(1)2(3)4)5wall 0best 0stack0top-1poppedunmatched ')': it becomes the new wall
s[0]')'popped -1, stack empty
stack[0]new base
Popping removed the old wall -1, so there was no open bracket for this ) to close. No valid substring can contain it, so its index 0 is pushed as the new wall; later runs are measured from just after it.
)0(1)2(3)4)5wall 1best 0stack01top'(' : push index 1
s[1]'('
stack[0, 1]top = 1
An open bracket might be matched later, so remember where it is. Its index 1 is now the top, which also makes it the wall if it is never matched: a run cannot reach back past an open bracket that is still waiting.
)0(1)2(3)4)5wall 0run 2best 2stack0top1poppedrun 2 is a new best
s[2]')'closes index 1
i − top2 − 0 = 2current run
best2
Popping 1 pairs it with this ). The top is now 0, the last index that is not part of a valid run, so everything from 1 to 2 is balanced: length 2.
)0(1)2(3)4)5wall 3best 2stack03top'(' : push index 3
s[3]'('
stack[0, 3]top = 3
An open bracket might be matched later, so remember where it is. Its index 3 is now the top, which also makes it the wall if it is never matched: a run cannot reach back past an open bracket that is still waiting.
)0(1)2(3)4)5wall 0run 4best 4stack0top3poppedrun 4 is a new best
s[4]')'closes index 3
i − top4 − 0 = 4current run
best4
Popping 3 pairs it with this ). The top is now 0, the last index that is not part of a valid run, so everything from 1 to 4 is balanced: length 4. That span takes in the pairs closed before this one too, which is why the wall, not the matching (, is what gets subtracted.
)0(1)2(3)4)5wall 5best 4stack5top0poppedunmatched ')': it becomes the new wall
s[5]')'popped 0, stack empty
stack[5]new base
Popping removed the old wall 0, so there was no open bracket for this ) to close. No valid substring can contain it, so its index 5 is pushed as the new wall; later runs are measured from just after it.
)0(1)2(3)4)5wall 5best 4stack5topreturn 4
best4indices 1…4
stack[5]walls left over
Answer 4. Red tiles are the brackets that never matched; they are exactly the walls valid runs could not cross. The longest stretch between two walls is the answer.
05

Dynamic programming

dp[i] is the length of the longest valid substring ending at i. A ) right after ( extends dp[i - 2] by 2; a ) after another ) looks past that run to index j and, if s[j] is (, wraps it and adds whatever valid run ends at j - 1.

▶1class Solution:
▶2 def longestValidParentheses(self, s: str) -> int:
▶3 dp = [0] * len(s)
▶4 best = 0
▶5 for i in range(1, len(s)):
▶6 if s[i] == ")":
▶7 if s[i - 1] == "(":
▶8 dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
▶9 else:
▶10 j = i - dp[i - 1] - 1
▶11 if j >= 0 and s[j] == "(":
▶12 dp[i] = dp[i - 1] + 2 + (dp[j - 1] if j >= 1 else 0)
▶13 best = max(best, dp[i])
▶14 return best
06

Common pitfalls

Counting matched pairs instead of contiguous length

✗ Wrong
if stack:
    stack.pop()
    pairs += 1
return 2 * pairs
✓ Right
stack.pop()
if not stack:
    stack.append(i)
else:
    best = max(best, i - stack[-1])

"()(()" has two matched pairs, so this returns 4, but the unmatched ( at index 2 splits them and the real answer is 2.

Measuring from the matching '(' instead of the wall

✗ Wrong
j = stack.pop()
best = max(best, i - j + 1)
✓ Right
stack.pop()
best = max(best, i - stack[-1])

That only measures the innermost pair plus what it encloses. In "()()" the second ) gets 2 instead of 4, because the run on its left is never added.

Skipping the -1 seed

✗ Wrong
stack = []
✓ Right
stack = [-1]

For "()" the pop empties the stack, so the ) is wrongly treated as unmatched and the answer comes out 0. The seed is the wall for runs that start at index 0.

Running the two-counter scan in one direction only

✗ Wrong
left-to-right pass only
✓ Right
left-to-right pass, then right-to-left pass

Left to right, "(()" never has equal counts, so it reports 0. The reverse pass, which resets when ( outnumbers ), finds the 2.

07

Edge cases

Empty string

The loop never runs and best stays 0.

08

Complexity

Time
O(n)
Space
O(n)
Each index is pushed once and popped at most once. The stack reaches n + 1 entries when every character is (. The two-counter scan in the FAQ brings space down to O(1).
09

Longest Valid Parentheses FAQ

How does the O(1) space two-pass method work?

Scan left to right with counters open and close. When they are equal, 2 * close is a valid length; when close exceeds open, reset both to 0. Then scan right to left with the roles swapped, resetting when open exceeds close. The first pass misses runs inside extra (, the second misses runs inside extra ), so together they find every run.

How is LeetCode 32 different from Valid Parentheses (LeetCode 20)?

LeetCode 20 asks whether the whole string is valid and has three bracket types, so the stack holds characters. LeetCode 32 has one bracket type but asks for the longest valid substring, so the stack holds indices and the unmatched ones mark where runs break.

Is the longest valid parentheses C++ code different from the Python one?

No. The longest valid parentheses Python code uses a list (append, pop, stack[-1]), the C++ version a stack<int> with top(), and Java an ArrayDeque<Integer> with peek(). The logic is line for line the same.

← Prev · #31
Next Permutation
Next · #33 →
Search in Rotated Sorted Array