Parentheses Problems: From Valid to Generate

Parentheses problems are a staple of coding interviews. They appear deceptively simple — just two characters, ( and ) — but they test deep understanding of stacks, recursion, dynamic programming, and BFS. This guide covers every major parentheses problem you’ll encounter, from the classic validation check to the tricky generation and removal variants.

1. Valid parentheses (LeetCode 20)

Given a string containing (, ), {, }, [, ], determine if the input is valid. Every open bracket must be closed by the same type in the correct order.

Stack approach

Push opening brackets onto a stack. When you see a closing bracket, check if the top of the stack is the matching opener:

def is_valid(s: str) -> bool:
    """Check if parentheses are valid. O(n) time, O(n) space."""
    stack = []
    matching = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in matching:
            # Closing bracket
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
        else:
            # Opening bracket
            stack.append(char)

    return len(stack) == 0

Time complexity: O(n) — single pass through the string. Space complexity: O(n) — the stack could hold all opening brackets.

Why this works

The stack enforces the nesting property. The most recently opened bracket must be closed first. A stack naturally models this “last in, first out” behavior. If we ever find a mismatch — or the stack is empty when we need a match — the string is invalid.

Common edge cases

• Empty string: valid (no brackets to mismatch)
• Single bracket: invalid
• Only opening brackets: invalid (stack won’t be empty at the end)
• "([)]": invalid (interleaved, not nested)
• "{[]}": valid (properly nested)

2. Generate parentheses (LeetCode 22)

Given n, generate all combinations of n pairs of well-formed parentheses. For n = 3, the output includes "((()))", "(()())", "(())()", "()(())", "()()()".

Backtracking approach

The key insight: at any point during construction, the number of closing brackets used must not exceed the number of opening brackets used.

def generate_parenthesis(n: int) -> list:
    """Generate all valid parentheses combinations. O(4^n / sqrt(n)) time."""
    result = []

    def backtrack(current: str, open_count: int, close_count: int):
        if len(current) == 2 * n:
            result.append(current)
            return

        # Can add opening bracket if we haven't used all n
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)

        # Can add closing bracket if it won't exceed opening count
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)

    backtrack('', 0, 0)
    return result

Time complexity: O(4^n / sqrt(n)) — this is the n-th Catalan number, which counts the number of valid parenthesizations. Space complexity: O(n) for the recursion stack (not counting the output).

Optimized with list (avoiding string concatenation)

String concatenation in Python creates a new string each time. Using a list and joining at the end is more efficient:

def generate_parenthesis_optimized(n: int) -> list:
    """Generate parentheses using list for efficiency."""
    result = []

    def backtrack(path: list, open_count: int, close_count: int):
        if len(path) == 2 * n:
            result.append(''.join(path))
            return

        if open_count < n:
            path.append('(')
            backtrack(path, open_count + 1, close_count)
            path.pop()

        if close_count < open_count:
            path.append(')')
            backtrack(path, open_count, close_count + 1)
            path.pop()

    backtrack([], 0, 0)
    return result

Understanding the recursion tree

For n = 2, the recursion tree looks like this:

                    ""
                   /
                  "("
                /     \
            "(("       "()"
            /            \
         "(()"          "()(
           |              |
         "(())"        "()()"

At each node, we branch left (add () if we have opens remaining, and branch right (add )) if closes are fewer than opens. This pruning eliminates all invalid sequences.

3. Longest valid parentheses (LeetCode 32)

Given a string containing only ( and ), find the length of the longest valid (well-formed) parentheses substring.

This is a hard problem with multiple elegant solutions.

Stack approach

Use a stack to track indices. Push the index of unmatched characters. The length of a valid substring is the gap between the current index and the top of the stack:

def longest_valid_parentheses_stack(s: str) -> int:
    """Find longest valid parentheses substring. O(n) time, O(n) space."""
    stack = [-1]  # Base index for calculating length
    max_len = 0

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # No matching opening bracket — push current as new base
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])

    return max_len

Why initialize with -1? The -1 acts as a sentinel. When we have a valid sequence starting from index 0, the length is i - (-1) = i + 1, which is correct.

**Walkthrough with s = "(()":

• i=0, (: push 0. Stack: [-1, 0]
• i=1, (: push 1. Stack: [-1, 0, 1]
• i=2, ): pop 1. Length = 2 - 0 = 2. Stack: [-1, 0]
• Answer: 2

DP approach

Define dp[i] = length of the longest valid parentheses ending at index i.

def longest_valid_parentheses_dp(s: str) -> int:
    """Longest valid parentheses using DP. O(n) time, O(n) space."""
    n = len(s)
    if n < 2:
        return 0

    dp = [0] * n
    max_len = 0

    for i in range(1, n):
        if s[i] == ')':
            if s[i - 1] == '(':
                # Case 1: "...()" — extends previous valid sequence
                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
            elif dp[i - 1] > 0:
                # Case 2: "...))" — check if there's a matching '(' before
                # the previous valid sequence
                j = i - dp[i - 1] - 1  # Index of potential matching '('
                if j >= 0 and s[j] == '(':
                    dp[i] = dp[i - 1] + 2
                    # Add any valid sequence before the matching '('
                    if j >= 1:
                        dp[i] += dp[j - 1]

            max_len = max(max_len, dp[i])

    return max_len

Two-pass approach: O(1) space

Scan left to right counting open and close brackets. When they’re equal, update the max. When close exceeds open, reset both. Then scan right to left (to catch cases like (()):

def longest_valid_parentheses_constant_space(s: str) -> int:
    """Longest valid parentheses with O(1) space. O(n) time."""
    max_len = 0

    # Left to right pass
    open_count = close_count = 0
    for char in s:
        if char == '(':
            open_count += 1
        else:
            close_count += 1

        if open_count == close_count:
            max_len = max(max_len, 2 * close_count)
        elif close_count > open_count:
            open_count = close_count = 0

    # Right to left pass
    open_count = close_count = 0
    for char in reversed(s):
        if char == '(':
            open_count += 1
        else:
            close_count += 1

        if open_count == close_count:
            max_len = max(max_len, 2 * open_count)
        elif open_count > close_count:
            open_count = close_count = 0

    return max_len

Why two passes? The left-to-right pass misses cases where there are excess opening brackets (like "(()") because close never catches up to open. The right-to-left pass handles this by detecting excess closing brackets instead.

4. Remove invalid parentheses (LeetCode 301)

Given a string with parentheses and letters, remove the minimum number of invalid parentheses to make the string valid. Return all possible results.

BFS approach

Use BFS to explore all possible strings with one removal. The first level where we find valid strings gives us the minimum removals:

from collections import deque

def remove_invalid_parentheses(s: str) -> list:
    """Remove minimum invalid parentheses. BFS approach."""
    def is_valid(string: str) -> bool:
        count = 0
        for c in string:
            if c == '(':
                count += 1
            elif c == ')':
                count -= 1
            if count < 0:
                return False
        return count == 0

    result = []
    visited = {s}
    queue = deque([s])
    found = False

    while queue:
        # Process all strings at current level
        level_size = len(queue)
        for _ in range(level_size):
            current = queue.popleft()

            if is_valid(current):
                result.append(current)
                found = True

            if found:
                continue  # Don't go deeper once we found valid strings

            # Try removing each parenthesis
            for i in range(len(current)):
                if current[i] not in '()':
                    continue
                candidate = current[:i] + current[i + 1:]
                if candidate not in visited:
                    visited.add(candidate)
                    queue.append(candidate)

        if found:
            break

    return result if result else [""]

Time complexity: O(2^n) in the worst case — we might explore many subsets. Space complexity: O(2^n) for the visited set.

Optimized: Calculate removals first

We can first calculate exactly how many ( and ) need to be removed, then use backtracking to find all valid results:

def remove_invalid_parentheses_optimized(s: str) -> list:
    """Optimized removal with pre-calculated counts."""
    # Calculate minimum removals needed
    open_rem = close_rem = 0
    for c in s:
        if c == '(':
            open_rem += 1
        elif c == ')':
            if open_rem > 0:
                open_rem -= 1
            else:
                close_rem += 1

    result = set()

    def backtrack(index: int, open_count: int, close_count: int,
                  open_rem: int, close_rem: int, path: list):
        if index == len(s):
            if open_rem == 0 and close_rem == 0:
                result.add(''.join(path))
            return

        char = s[index]

        # Option 1: Remove current character (if it's a parenthesis)
        if char == '(' and open_rem > 0:
            backtrack(index + 1, open_count, close_count,
                      open_rem - 1, close_rem, path)
        if char == ')' and close_rem > 0:
            backtrack(index + 1, open_count, close_count,
                      open_rem, close_rem - 1, path)

        # Option 2: Keep current character
        path.append(char)
        if char == '(':
            backtrack(index + 1, open_count + 1, close_count,
                      open_rem, close_rem, path)
        elif char == ')':
            if close_count < open_count:  # Only keep if valid
                backtrack(index + 1, open_count, close_count + 1,
                          open_rem, close_rem, path)
        else:
            # Regular character — always keep
            backtrack(index + 1, open_count, close_count,
                      open_rem, close_rem, path)
        path.pop()

    backtrack(0, 0, 0, open_rem, close_rem, [])
    return list(result)

5. Minimum add to make valid (LeetCode 921)

Given a string of parentheses, find the minimum number of parentheses to add to make it valid:

def min_add_to_make_valid(s: str) -> int:
    """Minimum additions to make parentheses valid. O(n) time, O(1) space."""
    open_needed = 0   # Unmatched '(' needing a ')'
    close_needed = 0  # Unmatched ')' needing a '('

    for char in s:
        if char == '(':
            open_needed += 1
        elif char == ')':
            if open_needed > 0:
                open_needed -= 1  # Matched with a previous '('
            else:
                close_needed += 1  # Need an extra '('

    return open_needed + close_needed

Time complexity: O(n). Space complexity: O(1).

The logic is clean: track unmatched opens and unmatched closes. The total additions needed is their sum.

6. Score of parentheses (LeetCode 856)

Given a balanced parentheses string, compute its score:

• () has score 1
• AB has score A + B (concatenation adds)
• (A) has score 2 * A (nesting doubles)

Stack approach

def score_of_parentheses(s: str) -> int:
    """Compute score of balanced parentheses. O(n) time, O(n) space."""
    stack = [0]  # Stack of scores at each depth level

    for char in s:
        if char == '(':
            stack.append(0)  # Start new depth level
        else:
            inner = stack.pop()
            # If inner is 0, this is "()" -> score 1
            # Otherwise this is "(A)" -> score 2 * A
            score = max(1, 2 * inner)
            stack[-1] += score

    return stack[0]

**Walkthrough with "(()(()))":

• (: stack = [0, 0]
• (: stack = [0, 0, 0]
• ): pop 0, score = max(1, 0) = 1, stack = [0, 1]
• (: stack = [0, 1, 0]
• (: stack = [0, 1, 0, 0]
• ): pop 0, score = 1, stack = [0, 1, 1]
• ): pop 1, score = 2, stack = [0, 3]
• ): pop 3, score = 6, stack = [6]
• Answer: 6

O(1) space approach

The score of () at depth d is 2^d. We just need to track the depth and sum up:

def score_of_parentheses_constant_space(s: str) -> int:
    """Score with O(1) space. O(n) time."""
    depth = 0
    score = 0

    for i, char in enumerate(s):
        if char == '(':
            depth += 1
        else:
            depth -= 1
            if s[i - 1] == '(':
                # This is a "()" pair at current depth
                score += 1 << depth  # 2^depth

    return score

Why this works: Every () pair contributes 2^depth to the total score. Nesting multiplies by 2, which is the same as incrementing the exponent. We only need to count the leaf () pairs and their depths.

7. Check valid string with wildcards (LeetCode 678)

Given a string with (, ), and * (wildcard that can be (, ), or empty), check if it can be valid:

def check_valid_string(s: str) -> bool:
    """Check validity with wildcards. O(n) time, O(1) space."""
    # Track the range of possible open bracket counts
    lo = 0  # Minimum possible open count
    hi = 0  # Maximum possible open count

    for char in s:
        if char == '(':
            lo += 1
            hi += 1
        elif char == ')':
            lo -= 1
            hi -= 1
        else:  # '*'
            lo -= 1  # Treat as ')'
            hi += 1  # Treat as '('

        if hi < 0:
            return False  # Too many closing brackets
        lo = max(lo, 0)  # lo can't go negative

    return lo == 0

The insight: Instead of tracking exact counts, track the range [lo, hi] of possible open bracket counts. If the range ever goes entirely negative, it’s invalid. At the end, 0 must be in the range.

Big-O summary

Problem	Time	Space
Valid parentheses	O(n)	O(n)
Generate parentheses	O(4^n / sqrt(n))	O(n)
Longest valid parentheses (stack)	O(n)	O(n)
Longest valid parentheses (two-pass)	O(n)	O(1)
Remove invalid parentheses (BFS)	O(2^n)	O(2^n)
Minimum add to make valid	O(n)	O(1)
Score of parentheses	O(n)	O(1)
Valid string with wildcards	O(n)	O(1)

Practice problems

1. Valid Parentheses (LeetCode 20) — Stack basics
2. Generate Parentheses (LeetCode 22) — Backtracking with constraints
3. Longest Valid Parentheses (LeetCode 32) — Stack or DP, both worth knowing
4. Remove Invalid Parentheses (LeetCode 301) — BFS for minimum removal
5. Minimum Add to Make Parentheses Valid (LeetCode 921) — Greedy counting
6. Score of Parentheses (LeetCode 856) — Stack or depth-based scoring
7. Valid Parenthesis String (LeetCode 678) — Range tracking with wildcards
8. Minimum Remove to Make Valid Parentheses (LeetCode 1249) — Stack + set
9. Check if a Parentheses String Can Be Valid (LeetCode 2116) — Locked positions variant

Key takeaways

• Stack is the default tool for parentheses validation. Push openers, pop on closers, check for empty at the end.
• Backtracking with constraints (open < n, close < open) generates all valid combinations efficiently by pruning the search tree.
• Longest valid parentheses has three approaches: stack (index-based), DP, and two-pass counting. The two-pass approach is O(1) space and elegant.
• BFS finds minimum removals naturally — the first level with valid strings is the answer.
• Greedy counting (tracking unmatched opens and closes) solves simpler problems like minimum additions in O(1) space.
• Range tracking [lo, hi] handles wildcards by maintaining the set of possible states simultaneously.