← DSA Atlas
Dedicated problem page · #32

Longest Valid Parentheses

HardOne-Dimensional Dynamic ProgrammingIndex stack with sentinel baseStack of unmatched indices
Solve on LeetCode ↗
32
HardOne-Dimensional Dynamic ProgrammingStack of unmatched indicesIndex stack with sentinel base

Longest Valid Parentheses

Given a string s containing only the characters '(' and ')', return the length of the longest contiguous substring that is a well-formed (valid) parenthesis sequence.

Open official problem prompt ↗
In plain English

Measure the longest window of the string that is a balanced parenthesis expression.

Picture it like this

Marking the floor just behind you as a reference line; each time you close a matching pair you measure from your current spot back to the last reference line to see how long the balanced stretch is.

Example
Input
s = ")()())"
Output
4
Why
The substring "()()" from index 1 to 4 is valid and has length 4.
Constraints
0 <= s.length <= 3 * 10^4s[i] is '(' or ')'
Pattern lesson

See the pattern, then code

Index stack with sentinel base
Recognition clue

Matching parentheses over a contiguous window and measuring a length points to a stack that stores positions of unmatched characters.

↗
One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. Keep the index just before the current valid run on the stack; when a ')' closes a '(', the distance from the current index to the new stack top is the length of the valid run ending here.

New words, made simpleKnow these before the algorithm
Valid parentheses
Every open '(' has a matching later ')' and pairs are properly nested.
Boundary index
A position marking the character just before a valid run; -1 seeds the first run at index 0.
Unmatched index
A position on the stack whose parenthesis has not yet been closed.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force substring check

Quadratic; too slow for 3*10^4 length.

Test every substring for validity with a counter.

Time O(n^2)Space O(n)
Best choiceIndex stack with sentinel

Single pass, handles all boundaries cleanly.

Stack unmatched indices; measure runs against the top boundary.

Time O(n)Space O(n)
The rule we keep true

Invariant

The bottom of the stack is always the index just before the current valid run, and every other stack entry is an unmatched '(' index in increasing order.

Why this is correct

Reasoning

A ')' can only extend a valid run if there is a matching '(' to pop. After popping, the new stack top is the last position that is NOT part of the current balanced run, so current_index minus that top is exactly the length of the balanced substring ending here. When the stack empties, the ')' is itself unmatched and becomes a fresh boundary. Every character is pushed and popped at most once.

The algorithm in three movesSay these aloud before coding
1Initialize a stack holding -1 as the base boundary

i=2 ')': stack=[0], len=2-0=2

2Push the index of every '('

i=4 ')': stack=[0], len=4-0=4

3On ')', pop; if the stack empties, push this index as a new boundary

i=5 ')': stack empties -> push 5

4Otherwise the valid length is current index minus the new stack top; track the max

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
)0
(1
)2
(3
)4
)5
1 · Readstack=[-1]
2 · AskSeed the boundary.
3 · Update statestack=[-1], best=0
4 · ResultReady to measure runs from index 0.
Key takeaway

Indices 1..4 form the valid run '()()' of length 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Sentinel and best

    Starting the stack with -1 lets the first valid run at index 0 be measured as 0-(-1) without a special case.

  2. 2
    Lines 5-7Push opens

    Each '(' index is stored so a later ')' can pop it and know where the pair began.

  3. 3
    Lines 8-14Close and measure

    Pop for a ')'; if the stack is now empty the ')' is a new boundary, otherwise the gap to the new top is a valid length to compare against best.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty string returns 0
  • All opens '(((' returns 0
  • All closes ')))' returns 0
  • Fully valid '(())' returns its full length
  • Leading unmatched ')' correctly resets the boundary
!

Common beginner mistakes

  • Forgetting the initial -1 sentinel, which breaks length measurement for runs starting at index 0
  • Trying to count with a single balance counter, which fails on cases like '(()' that never rebalance
  • Pushing characters instead of indices, losing the positional information needed for length
Check your understanding

Why push the index of an unmatched ')' onto the stack instead of just discarding it?

More in One-Dimensional Dynamic Programming

#198House RobberTake-or-skip linear DP#322Coin ChangeUnbounded knapsack (min coins)#300Longest Increasing SubsequencePatience sorting (tails array)#5Longest Palindromic SubstringExpand around center#70Climbing StairsFibonacci-style linear DP#91Decode WaysFibonacci-style linear DP