Problem Description

You are given a string s that contains only bracket characters: '(', ')', '{', '}', '[' and ']'. Your task is to determine whether this string of brackets is valid.

A bracket string is considered valid when it follows these rules:

1. Same Type Matching: Every opening bracket must be closed by a bracket of the same type. For example, '(' must be closed by ')', not by ']' or '}'.

2. Correct Order: Brackets must be closed in the correct order. If you open bracket A then bracket B, you must close B before closing A. For example, "([)]" is invalid because the brackets are not closed in the correct order.

3. Complete Pairing: Every closing bracket must have a corresponding opening bracket that comes before it, and every opening bracket must have a corresponding closing bracket.

The valid bracket pairs are:

• '(' with ')'
• '[' with ']'
• '{' with '}'

For example:

• "()" is valid - single pair of matching brackets
• "()[]{}" is valid - multiple pairs in sequence
• "([{}])" is valid - properly nested brackets
• "(]" is invalid - mismatched bracket types
• "([)]" is invalid - incorrect closing order
• "(((" is invalid - unclosed brackets

The solution uses a stack data structure to track opening brackets and verify they match with their corresponding closing brackets in the correct order. When an opening bracket is encountered, it's pushed onto the stack. When a closing bracket is found, the algorithm checks if it matches the most recent unclosed opening bracket (the top of the stack).

Intuition

Think about how you would manually check if brackets are valid when reading through them left to right. When you see an opening bracket like '(', you need to remember it and wait for its matching closing bracket ')'. But here's the key insight: if there are nested brackets, the most recently opened bracket must be closed first before we can close the brackets that came before it.

This "last opened, first closed" pattern is exactly how a stack works - Last In, First Out (LIFO). When we encounter an opening bracket, we need to "remember" it for later, so we push it onto a stack. When we see a closing bracket, it should match the most recent unclosed opening bracket, which is sitting at the top of our stack.

Consider the example "([)]". As we read through:

• '(' - push to stack: ['(']
• '[' - push to stack: ['(', '[']
• ')' - this should match with '(', but the top of stack is '[' - mismatch!

This immediately tells us the string is invalid because we're trying to close '(' before closing '['.

The beauty of this approach is that the stack naturally maintains the order of unclosed brackets for us. Every closing bracket we encounter must match with whatever is on top of the stack. If it doesn't match, or if the stack is empty when we try to pop (meaning there's a closing bracket with no corresponding opening bracket), we know the string is invalid.

At the end, if our stack is empty, it means every opening bracket found its matching closing bracket in the correct order. If the stack still has elements, it means some opening brackets were never closed.

The solution cleverly stores valid pairs as strings like '()', '[]', '{}' in a set, then checks if the popped opening bracket combined with the current closing bracket forms a valid pair by concatenating them and checking membership in this set.

Learn more about Stack patterns.

Solution Approach

The solution implements a stack-based approach to validate the bracket string. Here's a detailed walkthrough of the implementation:

Data Structures Used:

• A stack (stk) to keep track of opening brackets
• A set (d) containing valid bracket pairs as strings: {'()', '[]', '{}'}

Algorithm Steps:

1. Initialize the stack and valid pairs set:

   stk = []
   d = {'()', '[]', '{}'}

2. Iterate through each character in the string: For each character c in string s:

3. Check if it's an opening bracket:

   if c in '({[':
       stk.append(c)

   If the character is one of '(', '{', or '[', push it onto the stack. This stores the opening bracket for later matching.

4. Handle closing brackets:

   elif not stk or stk.pop() + c not in d:
       return False

   When we encounter a closing bracket (anything else), we perform two checks:

   • Empty stack check: not stk - If the stack is empty, there's no corresponding opening bracket for this closing bracket, so return False
   • Matching check: stk.pop() + c not in d - Pop the top element from the stack (the most recent opening bracket) and concatenate it with the current closing bracket. If this combination doesn't form a valid pair in our set d, return False

5. Final validation:

   return not stk

   After processing all characters, check if the stack is empty. An empty stack means all opening brackets were properly closed. If the stack still contains elements, some opening brackets were never closed, making the string invalid.

Key Pattern - Stack for Bracket Matching: The stack pattern is perfect here because bracket matching follows a Last-In-First-Out (LIFO) principle. The most recently opened bracket must be closed first before closing any brackets that were opened before it.

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the string, as we traverse the string once
• Space Complexity: O(n) in the worst case when all characters are opening brackets and get pushed to the stack

The elegance of this solution lies in how it leverages the stack's LIFO property to naturally handle the nesting structure of brackets and the clever use of string concatenation with set membership to validate bracket pairs.

Example Walkthrough

Let's walk through the solution with the example string s = "{[()]}"

Initial Setup:

• Stack: [] (empty)
• Valid pairs set: {'()', '[]', '{}'}

Step-by-step execution:

Character 1: '{'

• This is an opening bracket (found in '({[')
• Push to stack
• Stack: ['{']

Character 2: '['

• This is an opening bracket
• Push to stack
• Stack: ['{', '[']

Character 3: '('

• This is an opening bracket
• Push to stack
• Stack: ['{', '[', '(']

Character 4: ')'

• This is a closing bracket (not in '({[')
• Check: Is stack empty? No, stack has elements
• Pop from stack: '('
• Form pair: '(' + ')' = '()'
• Check: Is '()' in valid pairs set? Yes!
• Continue processing
• Stack: ['{', '[']

Character 5: ']'

• This is a closing bracket
• Check: Is stack empty? No
• Pop from stack: '['
• Form pair: '[' + ']' = '[]'
• Check: Is '[]' in valid pairs set? Yes!
• Continue processing
• Stack: ['{']

Character 6: '}'

• This is a closing bracket
• Check: Is stack empty? No
• Pop from stack: '{'
• Form pair: '{' + '}' = '{}'
• Check: Is '{}' in valid pairs set? Yes!
• Continue processing
• Stack: []

Final Check:

• Is stack empty? Yes (not stk returns True)
• Result: Valid string!

Counter-example with s = "([)]":

Character 1: '(' → Push to stack → Stack: ['(']

Character 2: '[' → Push to stack → Stack: ['(', '[']

Character 3: ')' → Pop '[' from stack → Form pair '[)' → Not in valid pairs! → Return False

The algorithm correctly identifies this as invalid because we're trying to close '(' before closing '['.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the algorithm iterates through each character in the string exactly once. For each character, it performs constant-time operations: checking if the character is an opening bracket, appending to the stack, popping from the stack, and checking membership in the set d.

The space complexity is O(n), where n is the length of the string s. In the worst case, when all characters in the string are opening brackets (like "(((((("), the stack will store all n characters. The dictionary d uses constant space O(1) since it always contains exactly 3 elements regardless of input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Check for Empty Stack Before Popping

One of the most common mistakes is attempting to pop from the stack without first checking if it's empty. This happens when encountering a closing bracket with no corresponding opening bracket.

Incorrect Implementation:

def isValid(self, s: str) -> bool:
    stack = []
    valid_pairs = {'()', '[]', '{}'}
  
    for char in s:
        if char in '({[':
            stack.append(char)
        else:
            # WRONG: This will raise an IndexError if stack is empty
            if stack.pop() + char not in valid_pairs:
                return False
  
    return not stack

What Goes Wrong:

• Input: ")("
• When processing the first ')', the stack is empty
• Calling stack.pop() raises an IndexError: pop from empty list

Correct Fix: Always check if the stack is empty before attempting to pop:

if not stack or stack.pop() + char not in valid_pairs:
    return False

2. Using Dictionary Instead of Set for Validation

Another pitfall is using a dictionary with opening brackets as keys and closing brackets as values, which complicates the matching logic unnecessarily.

Overly Complex Approach:

def isValid(self, s: str) -> bool:
    stack = []
    mapping = {'(': ')', '[': ']', '{': '}'}
  
    for char in s:
        if char in mapping:  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack:
                return False
            top = stack.pop()
            if mapping[top] != char:  # More complex matching logic
                return False
  
    return not stack

Why the Set Approach is Better:

• The set approach ({'()', '[]', '{}'}) with string concatenation is more concise
• It eliminates the need for separate logic to map opening to closing brackets
• The validation becomes a simple set membership check: stack.pop() + char in valid_pairs

3. Not Handling the Final Stack Check

Some implementations forget to verify that the stack is empty at the end, leading to false positives for strings with unclosed brackets.

Incorrect Implementation:

def isValid(self, s: str) -> bool:
    stack = []
    valid_pairs = {'()', '[]', '{}'}
  
    for char in s:
        if char in '({[':
            stack.append(char)
        else:
            if not stack or stack.pop() + char not in valid_pairs:
                return False
  
    # WRONG: Forgot to check if stack still has unclosed brackets
    return True  # Should be: return not stack

What Goes Wrong:

• Input: "((("
• All characters are pushed to the stack
• The function returns True even though there are three unclosed opening brackets
• The correct behavior should return False because not stack would be False

Correct Fix: Always return not stack instead of True to ensure all opening brackets were properly closed.