Bracket and Parentheses Matching

The Classic: Valid Parentheses

Given a string containing only the characters (, ), {, }, [, and ], determine whether it is valid. A string is valid if every open bracket is closed by the same type of bracket in the correct order. This is LeetCode 20, Valid Parentheses, and it is one of the most frequently asked easy problems in interviews, not because it is hard, but because it cleanly tests whether you understand stacks.

Why a Counter Is Not Enough

If the problem only involved one type of bracket, say just parentheses, you could solve it with a simple counter. Increment when you see (, decrement when you see ), reject if the counter ever goes negative, and check that it is zero at the end. But the moment you introduce multiple bracket types, a counter falls apart. Consider the string ({)}. A counter would see one open, one open, one close, one close, balanced by count, but clearly { is not closed by ). You need to remember not just how many brackets are open, but which specific bracket was most recently opened. That is exactly what a stack gives you.

The Algorithm

The algorithm is beautifully simple. Walk through the string one character at a time. When you encounter an opening bracket ((, [, or {), push it onto the stack. When you encounter a closing bracket, check whether the stack is non-empty and whether the top of the stack is the matching opening bracket. If it matches, pop the stack and continue. If it does not match, or if the stack is empty (meaning there is nothing to match against), the string is invalid. After processing every character, the string is valid only if the stack is empty. Any leftover opening brackets mean something was never closed.

Walking Through "({[]})"

Let us trace through the string ({[]}) to see the stack in action.

• Read (. It is an opener, so push it. Stack: [(]
• Read {. Push it. Stack: [(, {]
• Read [. Push it. Stack: [(, {, []
• Read ]. It is a closer. The top of the stack is [, which matches ]. Pop it. Stack: [(, {]
• Read }. Top is {, which matches. Pop. Stack: [(]
• Read ). Top is (, which matches. Pop. Stack: []

The stack is empty, so the string is valid. Every opener found its matching closer in the right order.

Walking Through "({[}])"

Now let us try ({[}]), which looks similar but has a subtle swap.

• Read (. Push. Stack: [(]
• Read {. Push. Stack: [(, {]
• Read [. Push. Stack: [(, {, []
• Read }. It is a closer. The top of the stack is [, but } expects {. Mismatch, so return false immediately.

The string is invalid. The } tried to close the most recent opener, which was [, not {. This is exactly the kind of error that a simple counter would miss.

Code: Valid Parentheses

def is_valid(s: str) -> bool:
    stack = []
    match = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in match:
            if not stack or stack[-1] != match[c]:
                return False
            stack.pop()
        else:
            stack.append(c)
    return not stack

The hashmap match maps each closer to its expected opener. If the character is a closer (it is in the map), we check and pop. Otherwise it must be an opener, so we push. The final not stack check catches unmatched openers left behind.

Minimum Remove to Make Valid Parentheses

LeetCode 1249 asks a different question: given a string that may contain letters as well as parentheses, remove the minimum number of parentheses so that the remaining string is valid. Return the resulting string.

The key insight is that there are exactly two kinds of invalid parentheses: unmatched closing brackets (a ) with no corresponding ( before it) and unmatched opening brackets (a ( that never gets closed). We can handle each kind in a separate pass.

The Stack-of-Indices Approach

We use a stack of indices to identify all invalid parentheses in a single pass. Push the index of every ( onto the stack. When you see ), if the stack is non-empty, pop (we found a match); if the stack is empty, this ) is unmatched, so blank it out immediately. After the pass, any indices still on the stack are unmatched opens, so blank those too. Then join everything back together.

An alternative is a two-pass counter approach. In the first pass, scan left to right with a counter of open parentheses: increment on (, decrement on ), and mark any ) for removal when the counter is zero. In the second pass, scan right to left and do the symmetric thing to find unmatched opens. Both approaches run in $O(n)$ time, but the stack version handles everything in one pass.

Code: Minimum Remove to Make Valid Parentheses

def min_remove_to_make_valid(s: str) -> str:
    s = list(s)
    stack = []
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            if stack:
                stack.pop()
            else:
                s[i] = ''  # unmatched close
    for i in stack:
        s[i] = ''  # unmatched open
    return ''.join(s)

We convert the string to a list so we can blank out characters by index. The stack collects indices of unmatched (. When we encounter ), either it matches a pending ( (pop the stack) or it is unmatched (blank it out). After the loop, anything left in the stack is an unmatched open, so blank those too. Finally, join everything back together.

Longest Valid Parentheses

With LeetCode 32, Longest Valid Parentheses, the goal is to find the length of the longest substring that forms a valid parentheses sequence. This is a different flavor of problem entirely. We are not checking validity or removing characters. We are finding the longest contiguous valid segment.

The Stack-of-Indices Trick

The key idea is to push indices onto the stack, not characters. We initialize the stack with -1 as a base marker. Then we iterate through the string:

• When we see (, push its index onto the stack.
• When we see ), pop the top of the stack. If the stack is now empty, push the current index as the new base marker. If the stack is not empty, the length of the current valid substring is i - stack[-1], where stack[-1] is the index just before the start of this valid segment.

Why does this work? The stack always holds the index of the last unmatched position. When we pop a matching ( and look at what is now on top, we are looking at the boundary just before the current valid run started. The distance from that boundary to the current position is the length of the valid substring.

Walking Through ")()())"

Let us trace through the string )()()) (indices 0 through 5).

• Initialize stack: [-1].
• Index 0, ): Pop -1. Stack is now empty, so push 0 as the new base. Stack: [0].
• Index 1, (: Push 1. Stack: [0, 1].
• Index 2, ): Pop 1. Stack: [0]. Length = 2 - 0 = 2. Max so far: 2.
• Index 3, (: Push 3. Stack: [0, 3].
• Index 4, ): Pop 3. Stack: [0]. Length = 4 - 0 = 4. Max so far: 4.
• Index 5, ): Pop 0. Stack is empty, so push 5. Stack: [5].

The answer is 4, corresponding to the substring ()() at indices 1 through 4. Notice how the base marker at index 0 let us correctly measure the run of two consecutive valid pairs as a single valid substring of length 4, not two separate substrings of length 2.

Code: Longest Valid Parentheses

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]
    max_len = 0
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

Generate Parentheses

LeetCode 22 asks you to generate all combinations of n pairs of well-formed parentheses. This is not a validation problem. It is a generation problem, and the natural tool is backtracking.

At each step, you have a partially built string. You can add ( if you have not used all n opens yet. You can add ) if the number of closes so far is less than the number of opens so far (otherwise you would create an invalid prefix). When the string reaches length 2n, it is a complete valid combination, so add it to the results.

This is a classic decision tree. At each position you branch into at most two choices (add open or add close), pruning branches that would lead to invalid strings. The pruning conditions are simple: open_count < n to add (, and close_count < open_count to add ).

Code: Generate Parentheses

def generate_parenthesis(n: int) -> list[str]:
    result = []

    def backtrack(current: list[str], opens: int, closes: int):
        if len(current) == 2 * n:
            result.append(''.join(current))
            return
        if opens < n:
            current.append('(')
            backtrack(current, opens + 1, closes)
            current.pop()
        if closes < opens:
            current.append(')')
            backtrack(current, opens, closes + 1)
            current.pop()

    backtrack([], 0, 0)
    return result

The number of valid combinations is the nth Catalan number, C(n) = (2n choose n) / (n + 1). For n = 3 that is 5 combinations; for n = 4, 14. The backtracking explores exactly the valid combinations and nothing more, thanks to the pruning.

Decode String

Consider LeetCode 394: you are given a string like 3[a2[c]] and must decode it into accaccacc. Brackets can nest, and a number before [ means "repeat what is inside that many times." The nesting makes this a natural stack problem: when you hit a [, you need to remember the current string and the repeat count so you can come back to them when the matching ] appears.

The algorithm uses a stack of pairs: each entry holds the string built so far and the repeat count that applies to the upcoming bracket group. When we see a digit, we accumulate the full number (it can be multi-digit). When we see [, we push the current string and the current number onto the stack, then reset both. When we see ], we pop the saved string and repeat count, and set the current string to the saved string plus the current string repeated that many times. Any regular letter just appends to the current string.

Walking Through "3[a2[c]]"

• Read 3: current number = 3.
• Read [: Push ("", 3) onto the stack. Reset current string to "", number to 0.
• Read a: current string = "a".
• Read 2: current number = 2.
• Read [: Push ("a", 2). Reset current string to "", number to 0.
• Read c: current string = "c".
• Read ]: Pop ("a", 2). Current string = "a" + "c" * 2 = "acc".
• Read ]: Pop ("", 3). Current string = "" + "acc" * 3 = "accaccacc".

Code: Decode String

def decode_string(s: str) -> str:
    stack = []
    current = ""
    num = 0
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '[':
            stack.append((current, num))
            current, num = "", 0
        elif c == ']':
            prev_str, repeat = stack.pop()
            current = prev_str + current * repeat
        else:
            current += c
    return current

The stack never holds bracket characters. It holds the context we need to resume after a nested group closes. This is the same principle as a call stack in recursion, just made explicit.

Score of Parentheses

LeetCode 856 defines a scoring system for balanced parentheses strings: () has score 1, (A) has score 2 * A, and AB (two valid strings side by side) has score A + B. Given a balanced string, compute its score.

The stack-based approach tracks the score at each nesting depth. We start with a stack containing a single zero, the running score at the outermost level. When we see (, we push a new zero onto the stack, opening a new nesting level. When we see ), we pop the top value. If it was zero, this was a bare (), so it scores 1. If it was nonzero, this was (A), so it scores 2 * A. Either way, we add the result to the new top of the stack.

Walking Through "(()(()))"

• Start stack: [0].
• (: Push 0. Stack: [0, 0].
• (: Push 0. Stack: [0, 0, 0].
• ): Pop 0 (bare pair), add max(2*0, 1) = 1 to top. Stack: [0, 1].
• (: Push 0. Stack: [0, 1, 0].
• (: Push 0. Stack: [0, 1, 0, 0].
• ): Pop 0, add 1 to top. Stack: [0, 1, 1].
• ): Pop 1, add 2*1 = 2 to top. Stack: [0, 3].
• ): Pop 3, add 2*3 = 6 to top. Stack: [6].

The answer is 6. The structure is ( () (()) ): the inner () scores 1, the inner (()) scores 2, their sum is 3, and the outer wrapper doubles it to 6.

Code: Score of Parentheses

def score_of_parentheses(s: str) -> int:
    stack = [0]
    for c in s:
        if c == '(':
            stack.append(0)
        else:
            v = stack.pop()
            stack[-1] += max(2 * v, 1)
    return stack[0]

The expression max(2 * v, 1) neatly handles both rules: when v is 0 (a bare ()), the score is 1; when v is positive (a wrapped substring), the score is doubled.

Minimum Add to Make Parentheses Valid

For LeetCode 921: given a string of parentheses, what is the minimum number of parentheses you must add to make the entire string valid? Unlike LC 1249 where you remove characters, here you are inserting them.

The insight is simple: scan left to right, tracking how many opens are unmatched (open) and how many closes are unmatched (close). When you see (, increment open. When you see ), if there is a pending open, decrement open (it found its match); otherwise increment close (this close has no partner). At the end, open + close is the answer: each unmatched open needs a ) added, and each unmatched close needs a ( added.

Code: Minimum Add to Make Parentheses Valid

def min_add_to_make_valid(s: str) -> int:
    open_count = 0
    close_count = 0
    for c in s:
        if c == '(':
            open_count += 1
        elif open_count > 0:
            open_count -= 1
        else:
            close_count += 1
    return open_count + close_count

No stack needed: two counters suffice because we only have one bracket type and we do not need to track positions. This runs in $O(n)$ time and $O(1)$ space.

Remove Invalid Parentheses

LeetCode 301 asks you to remove the minimum number of invalid parentheses to make the string valid, and return all possible results. Unlike LC 1249 which returns any one valid result, here we need every distinct string achievable by removing the fewest parentheses.

BFS is the natural approach. The idea is to explore removals level by level. At the first level, we try removing zero characters: if the original string is valid, return it. At the next level, we try removing exactly one parenthesis from every position, check each result for validity, and if any are valid we collect them and stop. If none are valid, we continue to the next level (removing two), and so on. Because BFS explores in order of removal count, the first level that produces valid strings is guaranteed to be the minimum removal.

To avoid duplicate work, we use a set to track strings we have already enqueued. We only remove parenthesis characters (not letters), since removing a letter can never help fix a bracket mismatch.

Code: Remove Invalid Parentheses

from collections import deque

def remove_invalid_parentheses(s: str) -> list[str]:
    def is_valid(s: str) -> bool:
        count = 0
        for c in s:
            if c == '(':
                count += 1
            elif c == ')':
                count -= 1
            if count < 0:
                return False
        return count == 0

    result = []
    seen = {s}
    queue = deque([s])
    found = False
    while queue:
        for _ in range(len(queue)):
            curr = queue.popleft()
            if is_valid(curr):
                result.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                if curr[i] not in '()':
                    continue
                nxt = curr[:i] + curr[i + 1:]
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
        if found:
            break
    return result

Once we find any valid string at the current BFS level, we set found = True and stop generating new candidates. We still drain the rest of the current level to collect all valid strings at the same minimum removal count.

Complexity Analysis

For Valid Parentheses, we make a single pass through the string, doing $O(1)$ work per character (push or pop). Time is $O(n)$ and space is $O(n)$ in the worst case (a string of all openers).

For Minimum Remove, we again do a single pass plus a cleanup step, both $O(n)$. Space is $O(n)$ for the stack of indices.

For Longest Valid Parentheses, one pass at $O(n)$ time and $O(n)$ space for the stack. There is also a clever $O(1)$ space solution using two counters with two passes (left-to-right and right-to-left), but the stack approach is more intuitive and general.

For Generate Parentheses, the time and space are both $O(4^n / \sqrt{n})$, which is the order of the nth Catalan number times the string length. In practice the output size dominates, and there is no way to do better since you must enumerate all valid strings.

For Decode String, each character is processed once and each stack entry is pushed and popped once, so time is $O(n \cdot m)$ where $m$ is the maximum nesting depth multiplied by repeat factors (the output can be exponentially larger than the input in theory). Space is $O(n)$ for the stack plus the size of the output string.

For Score of Parentheses, one pass at $O(n)$ time and $O(n)$ space for the stack (bounded by nesting depth).

For Minimum Add, we use two counters and a single pass: $O(n)$ time and $O(1)$ space.

For Remove Invalid Parentheses, BFS explores strings at each removal level. In the worst case the number of candidates is exponential, $O(2^n)$, and each candidate takes $O(n)$ to validate, giving $O(n \cdot 2^n)$ time. In practice the seen set and early stopping keep it manageable.

Across all these problems, the common thread is the stack. Whether you are pushing characters, indices, or counts, the stack is the natural data structure for anything involving nested matching. It captures the "most recent unmatched" relationship that parentheses problems always require.

Recognizing this pattern

You're probably looking at bracket matching when:

• The input contains literal brackets ((), [], {}, or HTML/XML tags) that must nest correctly.
• The problem says "valid" or "balanced" and the structure is LIFO: every open must close in reverse order of opening.
• You need the longest valid prefix or substring of a parentheses string.
• You're computing something (score, depth, removals) that depends on nesting level.

Common templates:

• Validate a bracket string: push opens, pop and match on closes, check the stack is empty at the end. Example: Valid Parentheses.
• Longest valid substring: keep indices on the stack and measure gaps between unmatched positions. Example: Longest Valid Parentheses.
• Minimum edits to balance: count unmatched opens and closes in a single pass. Example: Minimum Add to Make Parentheses Valid.
• Score by nesting depth: push on open, combine values on close using the depth captured by the stack. Example: Score of Parentheses.