32. Longest Valid Parentheses

How to solve Longest Valid Parentheses (LeetCode 32): the approach in brief

The problem

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Pattern

Longest Valid Parentheses is a Stack Patterns problem, in the Valid Parentheses Matching subpattern. The pattern covers parentheses matching, monotonic stack, histogram, and expression evaluation

Master parentheses validation and balancing using stack. Handle multiple bracket types and minimum additions.

Approach outline

1. Consider using a stack to keep track of indices of characters as you traverse the string; this data structure can help you efficiently match parentheses.
2. Push the index of the last unmatched ')' or a sentinel value onto the stack before processing to help calculate lengths of valid substrings.
3. When you encounter '(', push its index onto the stack; when you encounter ')', pop from the stack and use the current index and the new top of the stack to determine the length of a valid substring.

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Longest Valid Parentheses has been reported in interviews at Amazon, Facebook, Apple, ByteDance.