32. Longest Valid Parentheses

At a Glance

• Topic: dp-1d
• Pattern: Dynamic Programming + Monotonic Stack
• Difficulty: Hard
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 32

Problem (one-liner)

Given a parentheses string s, return length of the longest well-formed (balanced) contiguous substring.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• Longest valid substring — usually DP index meaning “longest ending here” or stack of unmatched boundaries
• Cannot reorder — substring must be contiguous

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute — check each substring O(n^3) with validator — too slow.
• Stack with sentinel index — push -1 base; on ) pop or compute span — O(n) time O(n) space — classic.
• DP array — lengthEnding[index] recurrence — O(n) time O(n) space — optimal.

Optimal Solution

Go

func longestValidParentheses(word string) int {
	maxLength := 0
	stackIndexes := []int{}
	stackIndexes = append(stackIndexes, -1)
	for index := 0; index < len(word); index++ {
		character := word[index]
		if character == '(' {
			stackIndexes = append(stackIndexes, index)
			continue
		}
		stackIndexes = stackIndexes[:len(stackIndexes)-1]
		if len(stackIndexes) == 0 {
			stackIndexes = append(stackIndexes, index)
			continue
		}
		candidate := index - stackIndexes[len(stackIndexes)-1]
		if candidate > maxLength {
			maxLength = candidate
		}
	}
	return maxLength
}

JavaScript

function longestValidParentheses(word) {
  let maxLength = 0;
  const stackIndexes = [-1];
  for (let index = 0; index < word.length; index += 1) {
    const character = word[index];
    if (character === '(') {
      stackIndexes.push(index);
      continue;
    }
    stackIndexes.pop();
    if (stackIndexes.length === 0) {
      stackIndexes.push(index);
      continue;
    }
    const candidate = index - stackIndexes[stackIndexes.length - 1];
    if (candidate > maxLength) {
      maxLength = candidate;
    }
  }
  return maxLength;
}

Walkthrough

Index stack stores unmatched ( positions; sentinel -1 marks virtual boundary. On ), pop; if empty, push current ) as new sentinel—fresh baseline for future spans; else length currentIndex - new stack top.

Invariant: Between consecutive stack entries lies a completely scanned segment whose validity state is reset at sentinel updates.

Edge Cases

• Empty string — 0
• No valid substring — )))
• Entire string valid — length n

Pitfalls

• DP recurrence off-by-one when merging neighboring segments ((...)() chaining)
• Stack without sentinel — harder to measure spans after balanced closes

Similar Problems

• 20. Valid Parentheses — basic balance check (Easy stepping stone)
• 22. Generate Parentheses — enumerate structures (Medium)
• 84. Largest Rectangle in Histogram — stack + span width (Hard)

Variants

• Count valid substrings — stack/DP with counts per position.
• With * wildcards — 678. Valid Parenthesis String if present, else two-stack greedy.
• Longest in wrap-around ring — duplicate string trick with window.

Mind-Map Tags

#parentheses #monotonic-stack #sentinel-index #o-n-one-pass #span-length