How do you solve Longest Valid Parentheses?

Initialize a stack with -1 to represent the base index before the string starts. Iterate through the string, pushing indices of '(' onto the stack. For each ')', pop the top of the stack. If the stack becomes empty, push the current index as a new base. Otherwise, calculate the length of the current valid substring as the difference between the current index and the top of the stack, updating the maximum length found. This approach guarantees O(n) time and O(n) space.

Longest Valid Parentheses

Q: What is the time complexity of Longest Valid Parentheses?

O(n). Each character is processed once. Stack push and pop operations are O(1), so the entire string is scanned in linear time.

Q: What pattern does Longest Valid Parentheses use?

The Pattern: Stack (Index Tracking for Valid Parentheses) The Heuristic: Use a stack to store indices of unmatched '(' and the last unmatched ')' to track valid substring boundaries; the difference between current index and top of stack after popping reveals the length of the current valid substring.

Hard Monotonic Stack

Problem

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

0 ≤ s.length ≤ 3 * 10⁴
s[i] is '(' or ')'

Example

Input: s = "(()))())("

Output: 4

The longest valid parentheses substring is "(())" which has length 4. The algorithm uses a stack initialized with -1 to track indices of unmatched '(' characters and the last unmatched ')' index. Iterating through the string, it pushes indices of '(' and pops for ')'. When the stack is empty after a pop, it pushes the current index as a new base. Otherwise, it calculates the length of the current valid substring as the difference between the current index and the top of the stack, updating the maximum length found. This approach efficiently tracks valid substrings boundaries and lengths in a single pass.

Approach

Straightforward Solution

A brute-force approach checks all substrings and validates each, resulting in O(n^3) time complexity, which is infeasible for large inputs.

Core Observation

Valid parentheses substrings correspond to balanced pairs of '(' and ')' with correct nesting. Tracking indices of unmatched '(' and the last unmatched ')' allows calculation of valid substring lengths by measuring distances between indices.

Path to Optimal

Preview

The key insight is to use a stack to store indices of unmatched '(' characters and the last unmatched ')' index…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a stack with -1 to represent the base index before the string starts. Iterate through the string, pushing indices of '(' onto the stack…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character is processed once. Stack push and pop operations are O(1), so the entire string is scanned in linear time.

Space

O(n)

In the worst case, all characters are '(', so all indices are pushed onto the stack, requiring O(n) auxiliary space.

Pattern Spotlight

Stack (Index Tracking for Valid Parentheses)

Use a stack to store indices of unmatched '(' and the last unmatched ')' to track valid substring boundaries; the difference between current index and top of stack after popping reveals the length of the current valid substring.

Solution

Python

1class Solution:
  def longestValidParentheses(self, s: str) -> int:
      longest = 0
      stack = [-1]
5
      for i, char in enumerate(s):
          if char == '(':
              stack.append(i)
          else:
              stack.pop()
              if not stack:
                  stack.append(i)
              else:
                  longest = max(longest, i - stack[-1])
15
      return longest

Step-by-Step Solution

Initialize Tracking Variables for Longest Valid Substring

3longest = 0
4stack = [-1]

Objective

To set up variables that track the maximum length found and maintain indices of unmatched parentheses.

Key Insight

Initializing the longest length to zero and the stack with -1 provides a base for calculating lengths of valid substrings. The stack holds indices of unmatched '(' characters and the last unmatched ')' index, enabling length calculations by index differences.

Interview Quick-Check

Core Logic

The stack initialized with -1 serves as a base index for length calculations, allowing the algorithm to handle valid substrings starting at index 0.

State & Boundaries

The longest variable tracks the maximum valid substring length found so far.

Common Pitfalls & Bugs

Forgetting to initialize the stack with -1 leads to incorrect length calculations for substrings starting at the beginning.

Iterate Through String and Update Stack to Track Valid Parentheses

To process each character, updating the stack to maintain indices of unmatched '(' and last unmatched ')' and calculate valid substring lengths.

Return the Maximum Length of Valid Parentheses Found

To output the length of the longest valid parentheses substring after processing the entire string.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 4 Critical

stack = [-1]

Initialize the stack with -1 as a sentinel base index.

The initial -1 allows length calculations for valid substrings starting at index 0 by providing a base index to subtract from current indices.

Line 14 Critical

longest = max(longest, i - stack[-1])

Update the longest valid substring length using the difference between current index and top of the stack.

Calculating the length as current index minus the top of the stack gives the length of the current valid substring, enabling tracking of the maximum length found.

Line 8 Critical

stack.append(i)

Push the index of '(' onto the stack.

Storing indices of unmatched '(' allows the algorithm to match them later with ')' and calculate valid substring lengths.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why is the stack initialized with -1, and what role does it play in calculating valid substring lengths?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Longest Valid Parentheses from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Longest Valid Parentheses drill

or drill a free problem

1	`class Solution:`
2	`def longestValidParentheses(self, s: str) -> int:`
3	`longest = 0`
4	`stack = [-1]`
5
6	`for i, char in enumerate(s):`
7	`if char == '(':`
8	`stack.append(i)`
9	`else:`
10	`stack.pop()`
11	`if not stack:`
12	`stack.append(i)`
13	`else:`
14	`longest = max(longest, i - stack[-1])`
15
16	`return longest`