Parentheses

Parentheses problems involve validating, balancing, and manipulating bracket sequences. These problems test stack usage, greedy algorithms, and string manipulation skills.

Core Concepts

Bracket Types

Round: ( )
Square: [ ]
Curly:
Angle: < > (less common)

Key Properties

Valid: Every opening has matching closing in correct order
Balanced: Equal number of opening and closing
Well-formed: Properly nested, no interleaving

Key Patterns & Techniques

1. Stack for Validation

Push opening brackets
Pop and match closing brackets
Stack empty at end = valid
Time: O(n), Space: O(n)

2. Greedy Counting

Track balance (open - close)
Balance never negative, ends at 0
Faster than stack for single type
Time: O(n), Space: O(1)

3. Two-Pass Validation

Left-to-right: track open parentheses
Right-to-left: track close parentheses
Both passes must succeed

4. BFS/DFS for Generation

Generate all valid combinations
Backtracking with constraints
Remove minimum for validity

Common Approaches

Valid Parentheses (Stack)

def isValid(s: str) -> bool:
    """
    Check if parentheses are balanced using stack.
    Time: O(n), Space: O(n)
    """
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in s:
        if char in pairs:  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack or pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

Minimum Add to Make Valid

def minAddToMakeValid(s: str) -> int:
    """
    Minimum additions to make parentheses valid.
    Time: O(n), Space: O(1)
    """
    open_needed = 0  # Unmatched '('
    close_needed = 0  # Unmatched ')'
    
    for char in s:
        if char == '(':
            open_needed += 1
        else:  # ')'
            if open_needed > 0:
                open_needed -= 1  # Match with previous '('
            else:
                close_needed += 1  # Need '(' before this ')'
    
    return open_needed + close_needed

Minimum Remove to Make Valid

def minRemoveToMakeValid(s: str) -> str:
    """
    Remove minimum parentheses to make string valid.
    Time: O(n), Space: O(n)
    """
    # First pass: mark invalid ')'
    chars = list(s)
    stack = []
    
    for i, char in enumerate(chars):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                chars[i] = ''  # Mark for removal
    
    # Second pass: mark unmatched '('
    while stack:
        chars[stack.pop()] = ''
    
    return ''.join(chars)

Remove Invalid Parentheses (BFS)

def removeInvalidParentheses(s: str) -> List[str]:
    """
    Remove minimum parentheses to get all valid strings.
    Time: O(2^n), Space: O(n)
    """
    def isValid(s: str) -> bool:
        count = 0
        for char in s:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
                if count < 0:
                    return False
        return count == 0
    
    # BFS to find minimum removals
    queue = deque([s])
    visited = {s}
    result = []
    found = False
    
    while queue:
        current = queue.popleft()
        
        if isValid(current):
            result.append(current)
            found = True
        
        if found:
            continue
        
        # Try removing each parenthesis
        for i in range(len(current)):
            if current[i] not in '()':
                continue
            
            next_str = current[:i] + current[i+1:]
            
            if next_str not in visited:
                visited.add(next_str)
                queue.append(next_str)
    
    return result if result else [""]

Longest Valid Parentheses

def longestValidParentheses(s: str) -> int:
    """
    Find length of longest valid parentheses substring.
    Time: O(n), Space: O(n)
    """
    stack = [-1]  # Base for calculating length
    max_length = 0
    
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:  # ')'
            stack.pop()
            
            if not stack:
                # No matching '(', use as new base
                stack.append(i)
            else:
                # Calculate length of valid substring
                max_length = max(max_length, i - stack[-1])
    
    return max_length

Problems in This Category

020. Valid Parentheses

Easy | Frequency: 74.9%Stack-based validation for multiple bracket types.

001. Minimum Remove to Make Valid

Medium | Frequency: 100.0%Two-pass algorithm to mark and remove invalid parentheses.

052. Minimum Add to Make Valid

Medium | Frequency: 51.9%Greedy counting of unmatched parentheses.

056. Remove Invalid Parentheses

Hard | Frequency: 47.0%BFS to find all valid strings with minimum removals.

Complexity Characteristics

Pattern	Time Complexity	Space Complexity	When to Use
Stack Validation	O(n)	O(n)	Multiple bracket types
Greedy Count	O(n)	O(1)	Single bracket type
Two-Pass	O(n)	O(1) or O(n)	Mark and remove
BFS Generation	O(2^n)	O(n)	Find all valid strings
DP	O(n²)	O(n)	Longest valid substring

Interview Tips

Pattern Recognition

“Valid parentheses?” → Stack for multiple types, counting for single
“Minimum add/remove” → Greedy counting or two-pass
“All valid strings” → BFS/DFS with minimum removals
“Longest valid substring” → Stack or DP
“Generate all valid” → Backtracking with constraints

Common Mistakes

Not handling multiple bracket types correctly
Forgetting to check if stack is empty before popping
Not checking if final stack is empty
Confusing “add” vs “remove” operations
Not considering empty string as valid

Key Insights

Stack for validation - classic pattern for nested structures
Greedy for single type - O(1) space, track open count
Balance never negative - more ’)’ than ’(’ is invalid
Two-pass for removal - mark invalid in both directions
BFS for minimum - level-by-level finds minimum removals
DP for longest - track valid substring lengths

Validation Approaches

Stack Method (Multiple Types)

def isValid(s: str) -> bool:
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in s:
        if char in pairs:
            stack.append(char)
        elif not stack or pairs[stack.pop()] != char:
            return False
    
    return not stack

Counter Method (Single Type)

def isValid(s: str) -> bool:
    balance = 0
    
    for char in s:
        if char == '(':
            balance += 1
        elif char == ')':
            balance -= 1
            if balance < 0:
                return False
    
    return balance == 0

Advanced Patterns

Generate Parentheses (Backtracking)

def generateParenthesis(n: int) -> List[str]:
    """
    Generate all valid parentheses combinations.
    Time: O(4^n / sqrt(n)) - Catalan number
    Space: O(n) for recursion
    """
    result = []
    
    def backtrack(path: str, open_count: int, close_count: int):
        # Base case
        if len(path) == 2 * n:
            result.append(path)
            return
        
        # Add '(' if we can
        if open_count < n:
            backtrack(path + '(', open_count + 1, close_count)
        
        # Add ')' if it would be valid
        if close_count < open_count:
            backtrack(path + ')', open_count, close_count + 1)
    
    backtrack('', 0, 0)
    return result

Score of Parentheses

def scoreOfParentheses(s: str) -> int:
    """
    Calculate score: () = 1, AB = A + B, (A) = 2 * A.
    Time: O(n), Space: O(n)
    """
    stack = [0]  # Stack of scores
    
    for char in s:
        if char == '(':
            stack.append(0)
        else:  # ')'
            top = stack.pop()
            # () scores 1, (A) scores 2*A
            stack[-1] += max(2 * top, 1)
    
    return stack[0]

Different Ways to Add Parentheses

def diffWaysToCompute(expression: str) -> List[int]:
    """
    Compute all possible results with different parenthesizations.
    Time: O(2^n), Space: O(2^n)
    """
    # Base case: single number
    if expression.isdigit():
        return [int(expression)]
    
    results = []
    
    for i, char in enumerate(expression):
        if char in '+-*':
            # Divide: compute left and right parts
            left = diffWaysToCompute(expression[:i])
            right = diffWaysToCompute(expression[i+1:])
            
            # Combine results
            for l in left:
                for r in right:
                    if char == '+':
                        results.append(l + r)
                    elif char == '-':
                        results.append(l - r)
                    else:  # '*'
                        results.append(l * r)
    
    return results

Valid Parenthesis String (Wildcard)

def checkValidString(s: str) -> bool:
    """
    Check validity with '*' as '(', ')', or empty.
    Time: O(n), Space: O(1)
    """
    # Track range of possible open parentheses count
    min_open = max_open = 0
    
    for char in s:
        if char == '(':
            min_open += 1
            max_open += 1
        elif char == ')':
            min_open -= 1
            max_open -= 1
        else:  # '*'
            min_open -= 1  # Treat as ')'
            max_open += 1  # Treat as '('
        
        # Can't have more ')' than '('
        if max_open < 0:
            return False
        
        # Keep min_open non-negative
        min_open = max(min_open, 0)
    
    # Must be possible to have 0 open at end
    return min_open == 0

Decision Tree

What's the goal?
├─ Validate parentheses
│  ├─ Multiple types? → Stack
│  └─ Single type? → Counter (O(1) space)
├─ Make valid
│  ├─ Add minimum? → Greedy counting
│  ├─ Remove minimum? → Two-pass marking
│  └─ All valid strings? → BFS with minimum removals
├─ Generate valid
│  └─ All combinations? → Backtracking
└─ Calculate property
   ├─ Longest valid? → Stack or DP
   └─ Score? → Stack with calculation

Pro Tip: For validation, use stack when you have multiple bracket types. For single type, greedy counting with O(1) space is better. For removal problems, mark invalid brackets in two passes (left-to-right and right-to-left) to handle both directions.

Get Started

Problem Categories

By Difficulty

Parentheses

Parentheses

Core Concepts

Bracket Types

Key Properties

Key Patterns & Techniques

1. Stack for Validation

2. Greedy Counting

3. Two-Pass Validation

4. BFS/DFS for Generation

Common Approaches

Valid Parentheses (Stack)

Minimum Add to Make Valid

Minimum Remove to Make Valid

Remove Invalid Parentheses (BFS)

Longest Valid Parentheses

Problems in This Category

020. Valid Parentheses

001. Minimum Remove to Make Valid

052. Minimum Add to Make Valid

056. Remove Invalid Parentheses

Complexity Characteristics

Interview Tips

Pattern Recognition

Common Mistakes

Key Insights

Validation Approaches

Stack Method (Multiple Types)

Counter Method (Single Type)

Advanced Patterns

Generate Parentheses (Backtracking)

Score of Parentheses

Different Ways to Add Parentheses

Valid Parenthesis String (Wildcard)

Decision Tree

Build docs developers (and LLMs) love

Get Started

Problem Categories

By Difficulty

​Parentheses

​Core Concepts

​Bracket Types

​Key Properties

​Key Patterns & Techniques

​1. Stack for Validation

​2. Greedy Counting

​3. Two-Pass Validation

​4. BFS/DFS for Generation

​Common Approaches

​Valid Parentheses (Stack)

​Minimum Add to Make Valid

​Minimum Remove to Make Valid

​Remove Invalid Parentheses (BFS)

​Longest Valid Parentheses

​Problems in This Category

020. Valid Parentheses

001. Minimum Remove to Make Valid

052. Minimum Add to Make Valid

056. Remove Invalid Parentheses

​Complexity Characteristics

​Interview Tips

​Pattern Recognition

​Common Mistakes

​Key Insights

​Validation Approaches

​Stack Method (Multiple Types)

​Counter Method (Single Type)

​Advanced Patterns

​Generate Parentheses (Backtracking)

​Score of Parentheses

​Different Ways to Add Parentheses

​Valid Parenthesis String (Wildcard)

​Decision Tree

Build docs developers (and LLMs) love

Parentheses

Core Concepts

Bracket Types

Key Properties

Key Patterns & Techniques

1. Stack for Validation

2. Greedy Counting

3. Two-Pass Validation

4. BFS/DFS for Generation

Common Approaches

Valid Parentheses (Stack)

Minimum Add to Make Valid

Minimum Remove to Make Valid

Remove Invalid Parentheses (BFS)

Longest Valid Parentheses

Problems in This Category

Complexity Characteristics

Interview Tips

Pattern Recognition

Common Mistakes

Key Insights

Validation Approaches

Stack Method (Multiple Types)

Counter Method (Single Type)

Advanced Patterns

Generate Parentheses (Backtracking)

Score of Parentheses

Different Ways to Add Parentheses

Valid Parenthesis String (Wildcard)

Decision Tree