Stack crash course ↗ · 31

32. Longest Valid Parentheses

Find the length of the longest valid (well-formed) parentheses substring. A stack of indices — seeded with -1 as a base — turns each ) into an O(1) span measurement: i − stack.top().

● HardIndex StackDynamic ProgrammingTypeScript

PROBLEM What we're solving

Given a string of only ( and ), return the length of the longest valid (correctly matched) parentheses substring. For ")()())" the answer is 4 — the substring "()()" at indices 1..4. For "(()" it is 2 (the inner "()"), and for "" it is 0.

KEY IDEA Measure spans against the last unmatched index

Insight → keep a stack holding the index of the last unmatched character — a base. When a ) successfully closes an opener, every position after that base up to the current i is valid, so the run length is simply i − base, where base = stack.top(). No re-scanning: one subtraction gives the length of the valid stretch ending here.

RECIPE Seed -1, push on open, pop-and-measure on close

1 · Seed the base. Push -1 onto an empty stack. It is the index just before a valid run could start, so the first valid span measures correctly as i − (−1).
2 · On (. Push its index i. We may need to close it later.
3 · On ). Pop first. If the stack is now empty, this ) had no opener — push i as the new base. Otherwise the pop matched an opener: update best = max(best, i − stack.top()).
4 · Answer. After the scan, best is the longest valid length.

Classic confusion → we push indices, not characters, and we pop before checking emptiness. Pushing chars loses position information — we could never compute a length. And the -1 sentinel is what lets a valid run that starts at index 0 measure as i − (−1) instead of mis-counting. When a stray ) empties the stack, it becomes the new base, so future spans are measured from the right place.

COST Complexity & alternatives

Brute force

O(n³)

Check every substring (O(n²) of them), validating each in O(n) with a counter.

Index stack

O(n)

One pass; each index pushed/popped once. O(n) stack space.

O(1)-space two-pass alternative

You can drop the stack entirely with two linear sweeps of counters. Left-to-right, track open and close counts: when equal, candidate length is 2·close; if close > open, reset both to 0. Then sweep right-to-left with the roles reversed (resetting when open > close) to catch runs like "(()" that never re-balance left-to-right. That is O(n) time and O(1) space. Dynamic programming (a dp[i] array of the longest valid run ending at i) also works in O(n) time, O(n) space.

Pattern transfer →the "stack of indices, measure spans by subtraction" move also powers Valid Parentheses (the matching core), Trapping Rain Water (widths between bars), and Largest Rectangle in Histogram (bar spans from popped indices).

RUN IT Index stack: length = i − stack top

string =

step 0 / 7

STARTScanning ")()())". Seed the stack with -1 as a base index and set best = 0.

1function longestValidParentheses(s: string): number {
2▶  const stack: number[] = [-1]; // base index: last unmatched position
3▶  let best = 0;
4 
5  for (let i = 0; i < s.length; i++) {
6    if (s[i] === '(') {
7      stack.push(i);            // remember this opener's index
8    } else {
9      stack.pop();              // try to close the most recent opener
10      if (stack.length === 0) {
11        stack.push(i);          // no base left → i is the new base
12      } else {
13        best = Math.max(best, i - stack[stack.length - 1]);
14      }
15    }
16  }
17  return best;
18}

s =)0(1)2(3)4)5

State

[-1]

stack

-1

top

—

curLen

best

current charpushed index / live lengthnew base (unmatched)best valid span

slowfast

TYPESCRIPT The solution, annotated

longestValidParentheses.ts
function longestValidParentheses(s: string): number {
  const stack: number[] = [-1]; // base index: last unmatched position
  let best = 0;

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);            // remember this opener's index
    } else {
      stack.pop();              // try to close the most recent opener
      if (stack.length === 0) {
        stack.push(i);          // no base left → i is the new base
      } else {
        best = Math.max(best, i - stack[stack.length - 1]);
      }
    }
  }
  return best;
}

Reading it block by block

Lines 2–3 — seed the base. The stack starts as [-1]. That -1 is a sentinel index sitting just before any possible valid run, so the first valid span measures correctly. best tracks the longest length seen.

Lines 6–7 — open. For every ( we push its index i. Storing the index (not the char) is what lets us later compute a length by subtraction.

Lines 8–11 — close, unmatched case. On ) we always pop. If the stack becomes empty, this ) had no opener to match: we push i to make it the new base for future spans.

Lines 12–13 — close, matched case. If the stack is non-empty after popping, the pop closed a real opener. Everything from the current base stack[stack.length - 1] up to i is valid, so the run length is i - stack[stack.length - 1]; we keep the max in best.

Line 17 — answer. After scanning every character, best holds the length of the longest valid parentheses substring.

Complexity → One pass over n characters; each index is pushed and popped at most once, so all stack work is amortized O(1). Total O(n) time and O(n) space for the stack. The two-pass counter variant achieves the same time in O(1) space.

INTERVIEWFollow-ups they'll ask

"Can you do it in O(1) space?" Yes — two passes of counters. Left-to-right track open/close; when equal record 2·close, when close > open reset both to 0. Then mirror it right-to-left (reset when open > close) to catch unbalanced-left runs like "(()".
"Show the DP formulation." Let dp[i] = longest valid run ending at i. Only ) can extend a run; combine with dp[i-1] and the character before that matched opener. O(n) time, O(n) space.
"Why seed the stack with -1 instead of starting empty?" So a valid run beginning at index 0 measures as i − (−1). Without it you'd special-case the empty stack on every match.
"Return the substring, not just its length." Track the i where each new best occurs; the span is [top + 1, i] at that moment.
"What about multiple bracket types?""Longest valid" with mixed brackets needs the matching logic of Valid Parentheses layered on; a mismatch resets the base just like a stray ) does here.

OPTIMAL Index Stack

longestValidParentheses.ts
function longestValidParentheses(s: string): number {
  const stack: number[] = [-1]; // base index: last unmatched position
  let best = 0;

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);            // remember this opener's index
    } else {
      stack.pop();              // try to close the most recent opener
      if (stack.length === 0) {
        stack.push(i);          // no base left → i is the new base
      } else {
        best = Math.max(best, i - stack[stack.length - 1]);
      }
    }
  }
  return best;
}

ALT 1 Dynamic programming — longest run ending at i

O(n) time · O(n) space

Build a dp array where dp[i] is the length of the longest valid substring ending exactly at i, extending earlier runs by reaching back over them.

approach-2.ts
function longestValidParentheses(s: string): number {
  const n = s.length;
  const dp: number[] = new Array(n).fill(0); // dp[i] = longest valid run ending at i
  let best = 0;

  for (let i = 1; i < n; i++) {
    if (s[i] !== ')') continue;             // only a ')' can close a run

    if (s[i - 1] === '(') {
      // "...()" — pair up with the immediately preceding '('
      dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
    } else {
      // "...))" — reach back over the inner valid run dp[i-1]
      const open = i - dp[i - 1] - 1;       // index that must hold the matching '('
      if (open >= 0 && s[open] === '(') {
        dp[i] = dp[i - 1] + 2 + (open >= 1 ? dp[open - 1] : 0);
      }
    }

    best = Math.max(best, dp[i]);
  }
  return best;
}

Note → When s[i-1] is also a ), the matching opener sits just before the inner run, at i − dp[i-1] − 1; we then also tack on any valid run that ended just before that opener (dp[open-1]) so adjacent groups merge.

ALT 2 Two-pass counters — no stack, O(1) space

O(n) time · O(1) space

Sweep once left-to-right and once right-to-left with two integer counters, recording a span whenever they balance and resetting whenever they go irrecoverably out of balance.

approach-3.ts
function longestValidParentheses(s: string): number {
  let best = 0;

  // Left-to-right: reset when ')' overtakes '(' (unmatched closer).
  let open = 0;
  let close = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') open++;
    else close++;
    if (open === close) best = Math.max(best, 2 * close);
    else if (close > open) open = close = 0;
  }

  // Right-to-left: reset when '(' overtakes ')' to catch runs like "(()".
  open = 0;
  close = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '(') open++;
    else close++;
    if (open === close) best = Math.max(best, 2 * open);
    else if (open > close) open = close = 0;
  }

  return best;
}

Note → The left pass alone misses strings such as "(()" where close never overtakes open; mirroring the scan from the right (resetting when open > close) recovers those runs. No extra data structure beyond two counters.

ALT 3 Brute force — validate every even-length substring

O(n³) time · O(n) space

Enumerate every even-length substring and test each for balance with a running counter — the baseline before any stack or DP insight.

approach-4.ts
function longestValidParentheses(s: string): number {
  const n = s.length;
  let best = 0;

  for (let i = 0; i < n; i++) {
    // Valid substrings have even length, so step j by 2.
    for (let j = i + 1; j < n; j += 2) {
      if (isValid(s, i, j)) {
        best = Math.max(best, j - i + 1);
      }
    }
  }
  return best;
}

function isValid(s: string, lo: number, hi: number): boolean {
  let balance = 0;
  for (let k = lo; k <= hi; k++) {
    balance += s[k] === '(' ? 1 : -1;
    if (balance < 0) return false; // a ')' with no opener before it
  }
  return balance === 0;
}

Note → There are O(n²) substrings and each validation is O(n), giving O(n³). It is only useful as a correctness reference: the index-stack, DP, and two-pass solutions all collapse this to a single linear pass.

MNEMONIC The one-liner

"Seed minus-one, push opener indices, on close pop then measure i minus the top."

TRIGGERS When you see _ → reach for _

"longest valid / well-formed substring"	stack of indices + base sentinel
need a length/span, not a yes/no	store indices, subtract i − top
stray closer breaks the run	push i as the new base
O(1) space required	two-pass open/close counters

SKELETON The reusable shape

skeleton.ts
function longestValidParentheses(s: string): number {
  const stack: number[] = [-1]; // sentinel base
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.length === 0) stack.push(i);            // new base
      else best = Math.max(best, i - stack[stack.length - 1]);
    }
  }
  return best;
}

FLASHCARDS Tap to flip

Why push indices onto the stack instead of characters?

Lengths are computed by subtraction (i − top). A character carries no position, so you could never measure a span.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What does ")()())" return?

QUESTION 02

Why does the stack store indices rather than the bracket characters?

QUESTION 03

What is the purpose of seeding the stack with -1?

QUESTION 04

On a ), after popping you find the stack is empty. What do you do?

QUESTION 05

What is the time and space complexity of the index-stack solution?

QUESTION 06

How can the same result be achieved in O(1) space?

QUESTION 07

For "(()", what is the answer?

QUESTION 08

#32 · Longest Valid ParenthesesFind the length of the longest valid parentheses substring. A stack of indices seeded with -1 as a base measures each valid span as i minus the stack top in one O(n) pass.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Measure spans against the last unmatched index

RECIPE Seed -1, push on open, pop-and-measure on close

COST Complexity & alternatives

O(1)-space two-pass alternative

RUN IT Index stack: length = i − stack top

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Index Stack

ALT 1 Dynamic programming — longest run ending at i

ALT 2 Two-pass counters — no stack, O(1) space

ALT 3 Brute force — validate every even-length substring

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _