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.

Recognition Cues

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

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