Leetcode 32. Longest Valid Parentheses

Let's understand what we're being asked to do. Given a string like '(()', we need to find the length of the longest substring where parentheses are properly balanced.

Tracing through '(()': The substring '()' at the end is balanced (length 2), but the full string is not balanced because there's an extra '(' at the start. So the answer is 2.

For '()(()', we have '()' at the start (length 2) and '()' at the end (length 2), but they're separated by an unmatched '('. The longest single balanced substring is 2.

Important constraint: We need a contiguous substring that is well-formed. We can't skip characters or combine non-adjacent valid segments.

Edge cases to consider: What if the entire string is balanced like '(())'? (return the full length). What if no valid substring exists like '((('? (return 0). What about empty string? (return 0).

The brute force approach checks every possible substring to see if it's balanced. For each starting position, try all ending positions and validate if that substring has matching parentheses. This requires checking if opening and closing counts match and that closing never exceeds opening at any point. While simple to understand, this approach is very inefficient as it examines all possible substrings.

def longest_valid_parentheses(s):
    """
    Brute force approach: Check every possible substring to see if it's balanced.
    For each starting position, try all ending positions and validate if that
    substring has matching parentheses.
    """
    max_length = 0
    n = len(s)
    
    # Try every possible starting position
    for start in range(n):
        # Try every possible ending position from this start
        for end in range(start + 2, n + 1, 2):  # Only even-length substrings can be valid
            # Extract substring
            substring = s[start:end]
            
            # Check if this substring is valid (balanced parentheses)
            if is_valid_parentheses(substring):
                # Update max length if this valid substring is longer
                max_length = max(max_length, end - start)
    
    return max_length
def is_valid_parentheses(s):
    """
    Helper function to check if a string has balanced parentheses.
    Returns True if opening and closing counts match and closing never exceeds opening.
    """
    open_count = 0
    
    # Scan through each character
    for char in s:
        if char == '(':
            # Increment count for opening parenthesis
            open_count += 1
        elif char == ')':
            # Decrement count for closing parenthesis
            open_count -= 1
            # If closing exceeds opening at any point, it's invalid
            if open_count < 0:
                return False
    
    # Valid only if all opening parentheses are matched
    return open_count == 0

A balanced substring has the property that at any point while reading left-to-right, the number of closing parentheses never exceeds the number of opening parentheses.

Additionally, at the end of a valid substring, the counts must be exactly equal. This means we need to track both the positions and the matching relationships.

Simply counting opening and closing parentheses isn't enough because '())()' has equal counts but isn't one valid substring.

We need to know where valid segments start and end. When we encounter a closing ')' that matches an opening '(', we can calculate the length of the valid substring ending at that position.

Think about checking if parentheses match: when you see '(', you're waiting for a future ')' to close it. When you see ')', you need to find its matching '('.

If we track the positions of unmatched opening parentheses, then when we see a closing parenthesis, we can find its match and calculate the length of the valid segment. The challenge is handling nested structures like '((()))' and adjacent segments like '()()'.

The optimal approach uses a stack to track the indices of unmatched parentheses. We push the index of each '(' onto the stack. When we see ')', we pop from the stack (matching it with the most recent unmatched '('). The key insight is maintaining a base index on the stack to calculate lengths: the current index minus the top of the stack gives us the length of the current valid substring. This efficiently handles both nested structures like '((()))' and adjacent segments like '()()'.

def longest_valid_parentheses(s):
    """
    Find the length of the longest valid (well-formed) parentheses substring.
    Uses a stack to track indices of unmatched parentheses.
    """
    # Initialize stack with base index -1
    stack = [-1]
    max_length = 0
    
    # Iterate through each character with its index
    for i in range(len(s)):
        if s[i] == '(':
            # Push index of '(' onto stack
            stack.append(i)
        else:
            # Pop from stack for ')'
            stack.pop()
            
            if not stack:
                # Stack empty: current ')' is unmatched, push as new base
                stack.append(i)
            else:
                # Calculate length: current index - top of stack
                current_length = i - stack[-1]
                max_length = max(max_length, current_length)
    
    return max_length

• Stack for position tracking: Use a stack to store indices (not characters) of parentheses - this allows you to calculate substring lengths by subtracting indices when matches are found, which is essential for finding the longest valid segment rather than just validating balance.
• Base index technique: Initialize the stack with -1 as a base reference point before processing - this handles the edge case where valid parentheses start at index 0, allowing you to calculate length as (current_index - stack.top()) without special conditions.
• Match-and-calculate pattern: When encountering ')', pop the stack first, then check if it's empty - if empty, push current index as new base; if not empty, calculate length from remaining top. This single pattern handles both tracking invalid positions and computing valid lengths.
• Dynamic programming alternative: The DP approach uses dp[i] to store the longest valid length ending at position i - when you find ')', look back at dp[i-1] to skip over the inner valid substring and check if there's a matching '(' before it, then add any valid substring before that match.
• Two-pass counter optimization: Scanning left-to-right tracking open/close counts, then right-to-left achieves O(1) space - reset counters when close > open (or open > close in reverse), and record max when open == close. This works because each pass catches what the other misses in unbalanced scenarios.
• Substring vs subsequence distinction: This problem requires contiguous valid parentheses (substring), not just any valid pairing - that's why we track positions/lengths continuously and reset on invalid characters, rather than just counting matches like in simpler balance-checking problems.