LeetCode 32: Longest Valid Parentheses

Problem Description

LeetCode Problem 32

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

Example 1:

Input: s = ”(()”
Output: 2
Explanation: The longest valid parentheses substring is ”()“.

Example 2:

Input: s = ”)()())”
Output: 4
Explanation: The longest valid parentheses substring is ”()()“.

Example 3:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 3 * 104
• s[i] is ’(’, or ’)‘.

Difficulty: Hard

Tags: string, dynamic programming, stack

Rating: 96.76%

Solution Approach

The key insight is that we can use a stack to keep track of the indices of unmatched parentheses, which helps us calculate the length of valid substrings.

Key Concepts

1. We use a stack to store indices rather than the parentheses characters themselves
2. We initialize the stack with -1, which serves as a base index for length calculation
3. The algorithm processes each character once, making decisions based on whether it’s an opening or closing parenthesis

Python Implementation

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s or len(s) < 2:
            return 0
        
        max_length = 0
        stack = [-1]  # Stack stores indices, initialize with -1 as base
        
        for i in range(len(s)):
            if s[i] == "(":
                # For opening parenthesis, push its index onto stack
                stack.append(i)
            else:
                # For closing parenthesis:
                # 1. Pop the top element (matching opening bracket or base)
                stack.pop()
                
                if not stack:
                    # If stack is empty, current index becomes new base
                    stack.append(i)
                else:
                    # Calculate length of valid substring up to current index
                    current_length = i - stack[-1]
                    max_length = max(max_length, current_length)
        
        return max_length

Detailed Walkthrough

Let’s trace through Example 2: ”)()())” step by step:

1. Initial state: stack = [-1], max_length = 0

2. Process ’)’ at index 0:

   • Pop -1 from stack
   • Stack is empty, so push 0
   • stack = [0]

3. Process ’(’ at index 1:

   • Push 1 to stack
   • stack = [0, 1]

4. Process ’)’ at index 2:

   • Pop 1 from stack
   • Calculate length: 2 - 0 = 2
   • max_length = 2
   • stack = [0]

5. Process ’(’ at index 3:

   • Push 3 to stack
   • stack = [0, 3]

6. Process ’)’ at index 4:

   • Pop 3 from stack
   • Calculate length: 4 - 0 = 4
   • max_length = 4
   • stack = [0]

7. Process ’)’ at index 5:

   • Pop 0 from stack
   • Stack is empty, so push 5
   • stack = [5]

Final result: max_length = 4

Why This Approach Works

The stack-based solution elegantly handles several challenges:

1. Nested Parentheses: By storing indices, we can handle nested valid sequences like ”(())“
2. Multiple Valid Sequences: We can track separate valid sequences in the string
3. Invalid Sequences: The base index (-1 or updated invalid indices) helps us reset our calculations when we encounter invalid sequences

Complexity Analysis

The solution has the following complexity characteristics:

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.