Valid Parentheses - Editorial

Overview

The "Valid Parentheses" problem is a classic string parsing challenge that tests your ability to recognize and manage nested structures. The core rule of the problem is that every closing bracket must match the most recently seen unclosed opening bracket.

Because we need to process the most recent items first, this problem perfectly aligns with the Last-In-First-Out (LIFO) property. This immediately hints at two possible approaches: simulating the reduction of matched pairs, or systematically tracking open brackets using a Stack data structure.

Brute force

A straightforward way to think about this problem is from the inside out. If a string is perfectly valid, it must contain at least one adjacent pair of matching brackets (like (), [], or {}).

If we repeatedly find these adjacent pairs and remove them, a valid string will eventually be reduced to an empty string. If the string is invalid, we will reach a point where no adjacent matching pairs exist, but the string is not empty (for example, (]).

def valid_parentheses(s: str) -> bool:
    # Continuously loop as long as there is a valid pair in the string
    while "()" in s or "[]" in s or "{}" in s:
        s = s.replace("()", "")
        s = s.replace("[]", "")
        s = s.replace("{}", "")
        
    # If the string is empty, all brackets were successfully matched
    return s == ""

• Time complexity: O(N^2) — In the worst-case scenario (e.g., ((((....))))), we make N/2 passes over the string. In each pass, the .replace() operation scans the string, taking O(N) time, resulting in quadratic time complexity.
• Space complexity: O(N) — Strings in Python are immutable. Every time we call .replace(), a new string is allocated in memory. In the worst case, this creates a sequence of strings that temporarily consume linear extra space.

Optimal / best approach

Instead of repeatedly modifying the string, we can process it in a single pass using a Stack.

As we iterate through the characters of the string:

1. If we encounter an open bracket ((, [, {), we push it onto the stack. It represents an "unclosed" bracket waiting for its match.
2. If we encounter a close bracket (), ], }), it must match the bracket at the top of the stack (the most recently opened one).
   • If the stack is empty, it means there is no corresponding open bracket. We return False.
   • If the top of the stack does not match the current close bracket, the brackets are mismatched. We return False.
   • If it matches, we pop the open bracket off the stack and continue.
3. Once we finish traversing the string, if the stack is completely empty, it means every open bracket found its closing partner. If it's not empty, some open brackets were left unclosed.

Using a hash map (dictionary) to store the bracket pairs makes the code much cleaner and easier to extend if new bracket types are introduced later.

def valid_parentheses(s: str) -> bool:
    stack = []
    # Map closing brackets to their corresponding opening brackets
    bracket_map = {")": "(", "]": "[", "}": "{"}
    
    for char in s:
        # If it's a closing bracket
        if char in bracket_map:
            # Pop the top element if stack isn't empty, otherwise assign a dummy value '#'
            top_element = stack.pop() if stack else '#'
            
            # If the popped element doesn't match the required opening bracket, it's invalid
            if bracket_map[char] != top_element:
                return False
        else:
            # It's an opening bracket, push to the stack
            stack.append(char)
            
    # If the stack is empty, all brackets were matched correctly
    return not stack

• Time complexity: O(N) — We traverse the given string exactly once. Dictionary lookups, stack pushes (append), and stack pops (pop) all operate in O(1) average time.
• Space complexity: O(N) — In the worst-case scenario (a string composed entirely of opening brackets like ((((((( ), all characters will be pushed onto the stack, requiring space proportional to the length of the string.

Edge cases to consider

• Odd-length strings: A valid string must have an even number of characters. While the optimal solution handles this gracefully, adding a quick check if len(s) % 2 != 0: return False at the very beginning can yield a tiny performance optimization by short-circuiting inherently invalid inputs.
• Starting with a close bracket: Inputs like ]() will trigger the if stack else '#' logic immediately, safely returning False without throwing an IndexError.
• Ending with an open bracket: Inputs like ()[ will leave the [ in the stack after the loop finishes. Returning not stack correctly evaluates to False.

Tools Pro

Gemini is AI and can make mistakes.