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.

Longest Valid Parentheses - LeetCode Solution

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.

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

The key insight is to use a stack to store indices of unmatched '(' characters and the last unmatched ')' index. This stack-based approach enables a single pass through the string, updating the longest valid substring length by calculating the difference between the current index and the index at the top of the stack after popping. This avoids rechecking substrings and reduces complexity to O(n).

Optimal Approach

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.

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.

Solution

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

1

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.

2

Iterate Through String and Update Stack to Track Valid Parentheses

6for 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])

Objective

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

Key Insight

Pushing indices of '(' onto the stack records potential start points for valid substrings. Upon encountering ')', popping the stack attempts to match a previous '('. If the stack empties, the current index is pushed as a new base, marking the boundary for future valid substrings. Otherwise, the difference between the current index and the top of the stack gives the length of the current valid substring, which updates the maximum length found. This approach efficiently tracks valid substring boundaries in a single pass.

Interview Quick-Check

Core Logic

The stack maintains indices of unmatched '(' and the last unmatched ')'; popping on ')' attempts to find a matching '(' and length calculation uses the difference between current index and top of stack.

State & Boundaries

If the stack becomes empty after popping, push the current index as a new base to mark the start of the next potential valid substring.

Common Pitfalls & Bugs

Failing to push the current index when the stack is empty after popping leads to incorrect length calculations and missed valid substrings.

Complexity

This single pass approach ensures O(n) time complexity with O(n) space for the stack.

3

Return the Maximum Length of Valid Parentheses Found

16	`return longest`

Objective

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

Key Insight

After iterating through the string and updating the longest valid substring length, returning this value provides the final answer. This value reflects the maximum length found using the stack-based tracking method.

Interview Quick-Check

Core Logic

Returning the longest variable gives the length of the longest valid parentheses substring found during the iteration.

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.

Line 10 Critical

stack.pop()

Pop the top index from the stack to attempt matching with current ')'.

Popping removes the last unmatched '(' index, simulating a match; if no match exists, the stack may become empty, indicating an unmatched ')'.

Line 12 Critical

stack.append(i)

Push the current index onto the stack as a new base when no unmatched '(' remain.

This index marks the boundary before the next valid substring can start, ensuring length calculations remain accurate.

Line 9 Core

else:

Handle the case where the current character is a closing parenthesis ')'.

Encountering ')' triggers an attempt to match with a previous '(' by popping the stack, which is critical for identifying valid substrings.

Line 11 Core

if not stack:

Check if the stack is empty after popping.

An empty stack means no unmatched '(' remain to match the current ')', so the current index becomes a new base for future valid substrings.

Line 3 Core

longest = 0

Initialize the variable to track the longest valid parentheses substring length.

This variable accumulates the maximum length found during iteration, enabling the algorithm to return the correct final result.

Line 7 Core

if char == '(':

Check if the current character is an opening parenthesis '('

Identifying '(' characters is essential to push their indices onto the stack as potential start points for valid substrings.

Line 13 Core

else:

Handle the case where the stack is not empty after popping.

A non-empty stack means a matching '(' was found; the top of the stack now marks the start of the current valid substring.

Line 16 Core

return longest

Return the maximum length of valid parentheses substring found.

This final return outputs the result of the algorithm after processing the entire string.

Line 6 Standard

for i, char in enumerate(s):

Iterate through each character and its index in the string.

Processing each character sequentially is necessary to evaluate all possible valid substrings and update tracking structures accordingly.

Test Your Understanding

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

The initial -1 acts as a sentinel base index to handle the edge case of a valid substring starting at index 0. It allows length calculation by subtracting the top of the stack from the current index, ensuring correct length measurement even when the valid substring starts at the beginning.

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`

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])`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Tracking Variables for Longest Valid Substring

Iterate Through String and Update Stack to Track Valid Parentheses

Return the Maximum Length of Valid Parentheses Found

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.