Longest Valid Parentheses | Leetcode 32

Welcome to one of the most notoriously difficult String problems on the platform: Longest Valid Parentheses (Leetcode 32). While standard parenthesis matching is typically a simple stack-based exercise, searching for the longest valid contiguous subset elevates the complexity drastically.

Problem Statement

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

Example 1: s = "(()" => Output: 2 (The longest valid substring is "()", which has a length of 2).

Example 2: s = ")()())" => Output: 4 (The longest valid substring is "()()").

Approach 1: Stack Architecture O(N) Time | O(N) Space

In traditional matching problems, we push opening brackets ( to the stack, and pop them when we see ). For this problem, we push the indices of the brackets instead of the characters themselves!

We seed the stack with -1 before doing anything. This acts as our "anchor" or absolute baseline.

1. If we see (, push its index.
2. If we see ), pop the top element.
   • If the stack immediately becomes empty, we just lost our anchor! We must push the current index to establish a brand-new baseline pointing at this broken parenthesis.
   • If the stack is NOT empty, we calculate the streak by subtracting the new stack top from our current index i.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_len = 0
        # Initialize stack with -1 to serve as the baseline anchor
        stack = [-1]
        
        for i, char in enumerate(s):
            if char == '(':
                # Push the index of the open parenthesis
                stack.append(i)
            else:
                # Pop the matching open parenthesis
                stack.pop()
                
                if not stack:
                    # Anchor broken! Establish the new floor boundary.
                    stack.append(i)
                else:
                    # Calculate valid contiguous distance from the new top
                    max_len = max(max_len, i - stack[-1])
                    
        return max_len

Complexity Analysis

Approach 2: Optimal Double Traversal O(N) Time | O(1) Space

Can we do it natively without spawning a massive O(N) stack? Yes! We can use two integer counters: left and right.

We scan the string from left-to-right:

• Every ( increments the left counter. Every ) increments the right counter.
• If left == right, we've found a perfectly matched chunk! The length is 2 * right. We update our max length.
• If right > left, the sequence is fundamentally shattered (we have a hanging closing bracket). We immediately reset both counters to 0.

The Catch: A left-to-right scan will fail to find the longest substring if the string is heavily left-skewed, like "(()". The counters will never equal each other, and it will return 0. So, we must repeat the exact same process scanning Right-to-Left, swapping our reset logic!

graph TD
    A["Scan Left-to-Right"] --> B{"chr == '(' ?"}
    B -- Yes --> C["left += 1"]
    B -- No --> D["right += 1"]
    
    C --> E{"left == right?"}
    D --> E
    E -- Yes --> F["max = max(max, 2 * right)"]
    E -- "right > left" --> G["RESET left=0, right=0"]
    
    A -.->|"Repeat entire logic Right-to-Left after ending"| ReverseScan

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        left, right, max_len = 0, 0, 0
        
        # Left to Right Pass
        for char in s:
            if char == '(': left += 1
            else: right += 1
            
            if left == right:
                max_len = max(max_len, 2 * right)
            elif right > left:
                left = right = 0
                
        # Right to Left Pass
        left = right = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '(': left += 1
            else: right += 1
                
            if left == right:
                max_len = max(max_len, 2 * left)
            elif left > right:
                left = right = 0
                
        return max_len

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (32)