Parenthesis — SWE Playbook

01 / 05

Introduction

Parenthesis balancing is a classic problem type inspired by compiler analysis. The key data structure is the stack (LIFO: last in, first out).

Two failure cases for unbalanced parentheses:
1. Unmatched closing: A closing paren with no matching open (e.g., "())")
2. Unmatched opening: Extra opening parens at the end (e.g., "(()")

The stack holds opening parentheses. When we see a closing paren, we try to match it with the top of the stack.

KEY INSIGHT

O(1) Space Optimization: For single-type parentheses "()", we don't need a stack - just a counter! We only care about the count of unmatched opening parens, not their positions.

TimeO(n)

SpaceO(n) for multi-type, O(1) for single-type

Multi-Type Validation

Handle multiple bracket types: (), [], {}. Use a dictionary to map closing to opening brackets.

pythonREFERENCE

def isValid(self, s: str) -> bool:
    paren = {')': '(', '}': '{', ']': '['}
    stack = []  # stack of opening brackets

    for c in s:
        if c in paren:  # closing bracket
            if not stack or stack[-1] != paren[c]:
                return False  # Case 1: no match
            stack.pop()  # matched!
        else:  # opening bracket
            stack.append(c)

    return not stack  # Case 2: extra opening brackets

Single-Type Validation (O(1) Space)

For single bracket type, use a counter instead of stack.

pythonREFERENCE

def isValid(s: str) -> bool:
    balance = 0
    for c in s:
        if c == '(':
            balance += 1
        elif c == ')':
            balance -= 1
        if balance < 0:
            return False  # Case 1: unmatched closing
    return balance == 0  # Case 2: unmatched opening

02 / 05

Wildcard Validation

When '*' can be '(', ')', or empty, use a greedy two-pass approach.

KEY INSIGHT

Two-pass greedy:
- Left-to-right: Treat all '*' as '(' - checks for unmatched ')'
- Right-to-left: Treat all '*' as ')' - checks for unmatched '('

If both passes succeed, there exists a valid assignment of wildcards.

Wildcard Validation Template

Greedy approach for parentheses with wildcards.

pythonREFERENCE

def checkValidString(self, s: str) -> bool:
    def check(s, open_char):
        balance = 0
        for c in s:
            if c == open_char or c == '*':
                balance += 1
            else:
                balance -= 1
            if balance < 0:
                return False
        return True

    # Check both directions
    return check(s, '(') and check(s[::-1], ')')

03 / 05

Minimum Operations

Problems asking for minimum insertions, deletions, or swaps to balance parentheses.

Minimum Additions

Count unmatched opening and closing brackets.

pythonREFERENCE

def minAddToMakeValid(self, s: str) -> int:
    open_count = 0  # unmatched '('
    close_needed = 0  # unmatched ')'

    for c in s:
        if c == '(':
            open_count += 1
        elif c == ')':
            if open_count > 0:
                open_count -= 1  # matched
            else:
                close_needed += 1  # need a '('

    return open_count + close_needed

Minimum Removals

Track indices of unmatched brackets to remove.

pythonREFERENCE

def minRemoveToMakeValid(self, s: str) -> str:
    remove = set()
    stack = []  # indices of '('

    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            if stack:
                stack.pop()  # matched
            else:
                remove.add(i)  # unmatched ')'

    remove.update(stack)  # unmatched '('
    return ''.join(c for i, c in enumerate(s) if i not in remove)

Minimum Swaps

For balanced count of '[' and ']', remove matched pairs first.

pythonREFERENCE

def minSwaps(self, s: str) -> int:
    # After removing matched pairs, we're left with "]]]..[[[" pattern
    # Each swap fixes 2 pairs, so answer is ceil(unmatched / 2)

    unmatched_open = 0
    for c in s:
        if c == '[':
            unmatched_open += 1
        elif unmatched_open > 0:
            unmatched_open -= 1  # matched, ignore

    return (unmatched_open + 1) // 2

04 / 05

Calculator Parsing

Parse and evaluate expressions with parentheses, operators, and operator precedence.

KEY INSIGHT

Key technique: Precompute matching parentheses with a stack. Then recursively parse subexpressions within each parenthesis pair.

For operator precedence (* / before + -), buffer the previous number and only add to result when seeing + or -.

Parenthesis Matching Precomputation

Map each opening bracket index to its matching closing index.

pythonREFERENCE

def precompute_matching(s):
    stack = []
    closing = {}  # opening_idx -> closing_idx

    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            open_idx = stack.pop()
            closing[open_idx] = i

    return closing

Basic Calculator Template

Handles +, -, *, / with parentheses. Works for Calculator I, II, III.

pythonREFERENCE

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(" ", "")
        self.closing = {}
        stack = []

        # Precompute matching parens
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == ')':
                self.closing[stack.pop()] = i

        return self.parse(s, 0, len(s) - 1)

    def parse(self, s: str, left: int, right: int) -> int:
        res, prev, op = 0, 0, '+'
        i = left

        while i <= right:
            if s[i] == '(':
                curr = self.parse(s, i + 1, self.closing[i] - 1)
                i = self.closing[i] + 1
            elif s[i].isdigit():
                j = i
                while j <= right and s[j].isdigit():
                    j += 1
                curr = int(s[i:j])
                i = j
            else:
                op = s[i]
                i += 1
                continue

            # Apply previous operator
            if op == '+':
                res += prev
                prev = curr
            elif op == '-':
                res += prev
                prev = -curr
            elif op == '*':
                prev *= curr
            elif op == '/':
                prev = int(prev / curr)

        return res + prev

05 / 05

Problems

Practice problems for parenthesis techniques.

WORKED PROBLEMS10

01Valid ParenthesesEasy

Given a string containing '(', ')', '{', '}', '[', ']', determine if it's valid.

pythonREFERENCE

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

TimeO(n)

SpaceO(n)

WHY IT WORKS

Classic stack problem. Push opening brackets, pop and match closing brackets.

Open practice view →Open original problem ↗

02Generate ParenthesesMedium

Generate all combinations of n pairs of well-formed parentheses.

pythonREFERENCE

def generateParenthesis(self, n: int) -> List[str]:
    res = []

    def backtrack(curr, open_count, close_count):
        if len(curr) == 2 * n:
            res.append(''.join(curr))
            return

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

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

    backtrack([], 0, 0)
    return res

TimeO(4^n / sqrt(n))

SpaceO(n)

WHY IT WORKS

Backtracking with pruning. Only add '(' if we have remaining, only add ')' if it won't exceed open count.

Open practice view →Open original problem ↗

03Valid Parenthesis StringMedium

Given string with '(', ')', and '*' (wildcard), determine if it can be valid.

pythonREFERENCE

def checkValidString(self, s: str) -> bool:
    def check(s, open_char):
        balance = 0
        for c in s:
            balance += 1 if c == open_char or c == '*' else -1
            if balance < 0:
                return False
        return True

    return check(s, '(') and check(s[::-1], ')')

TimeO(n)

SpaceO(1)

WHY IT WORKS

Greedy two-pass: first pass treats '*' as '(', second pass treats '*' as ')'. Both must succeed.

Open practice view →Open original problem ↗

04Minimum Add to Make Parentheses ValidMedium

Return minimum insertions to make parentheses string valid.

pythonREFERENCE

def minAddToMakeValid(self, s: str) -> int:
    open_count = 0
    close_needed = 0
    for c in s:
        if c == '(':
            open_count += 1
        elif open_count > 0:
            open_count -= 1
        else:
            close_needed += 1
    return open_count + close_needed

TimeO(n)

SpaceO(1)

WHY IT WORKS

Count unmatched '(' and unmatched ')' separately. Answer is their sum.

Open practice view →Open original problem ↗

05Minimum Remove to Make Valid ParenthesesMedium

Remove minimum parentheses to make string valid. Return any valid result.

pythonREFERENCE

def minRemoveToMakeValid(self, s: str) -> str:
    remove = set()
    stack = []
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        elif c == ')':
            if stack:
                stack.pop()
            else:
                remove.add(i)
    remove.update(stack)
    return ''.join(c for i, c in enumerate(s) if i not in remove)

TimeO(n)

SpaceO(n)

WHY IT WORKS

Track indices of unmatched brackets. Need stack (not counter) to know which indices to remove.

Open practice view →Open original problem ↗

06Minimum Swaps to Make String BalancedMedium

Given string with equal '[' and ']', find minimum swaps to balance.

pythonREFERENCE

def minSwaps(self, s: str) -> int:
    unmatched = 0
    for c in s:
        if c == '[':
            unmatched += 1
        elif unmatched > 0:
            unmatched -= 1
    return (unmatched + 1) // 2

TimeO(n)

SpaceO(1)

WHY IT WORKS

After removing matched pairs, we have "]]][[[" pattern. Each swap fixes 2 brackets, so ceil(unmatched/2).

Open practice view →Open original problem ↗

07Number of AtomsHard

Parse a chemical formula and return atom counts in sorted order. Parenthesized groups can be followed by multipliers.

pythonREFERENCE

from collections import Counter

def countOfAtoms(self, formula: str) -> str:
    n = len(formula)
    closing = {}
    stack = []
    for i, c in enumerate(formula):
        if c == '(':
            stack.append(i)
        elif c == ')':
            closing[stack.pop()] = i

    def read_number(i):
        start = i
        while i < n and formula[i].isdigit():
            i += 1
        return (int(formula[start:i]) if i > start else 1), i

    def parse(left, right):
        counts = Counter()
        i = left
        while i <= right:
            if formula[i] == '(':
                close = closing[i]
                inner = parse(i + 1, close - 1)
                multiplier, i = read_number(close + 1)
                for atom, count in inner.items():
                    counts[atom] += count * multiplier
            else:
                j = i + 1
                while j <= right and formula[j].islower():
                    j += 1
                atom = formula[i:j]
                multiplier, i = read_number(j)
                counts[atom] += multiplier
        return counts

    counts = parse(0, n - 1)
    return ''.join(atom + (str(count) if count > 1 else '') for atom, count in sorted(counts.items()))

TimeO(n log a)

SpaceO(n)

WHY IT WORKS

This follows the same recursive parsing pattern as calculators: match parentheses, parse the inner expression, then apply the multiplier after the closing parenthesis.

Open practice view →Open original problem ↗

08Decode StringMedium

Decode "3[a2[c]]" = "accaccacc". k[encoded] means repeat k times.

pythonREFERENCE

def decodeString(self, s: str) -> str:
    # Precompute matching brackets
    closing = {}
    stack = []
    for i, c in enumerate(s):
        if c == '[':
            stack.append(i)
        elif c == ']':
            closing[stack.pop()] = i

    def parse(left, right):
        res = []
        i = left
        while i <= right:
            if s[i].isalpha():
                res.append(s[i])
                i += 1
            elif s[i].isdigit():
                j = i
                while s[j].isdigit():
                    j += 1
                k = int(s[i:j])
                inner = parse(j + 1, closing[j] - 1)
                res.append(inner * k)
                i = closing[j] + 1
        return ''.join(res)

    return parse(0, len(s) - 1)

TimeO(n × max_k)

SpaceO(n)

WHY IT WORKS

Precompute bracket matching, then recursively parse. Similar pattern to calculator problems.

Open practice view →Open original problem ↗

09Different Ways to Add ParenthesesMedium

Return all possible results from computing expression with different groupings.

pythonREFERENCE

def diffWaysToCompute(self, expression: str) -> List[int]:
    @cache
    def dp(s):
        if s.isdigit():
            return [int(s)]

        res = []
        for i, c in enumerate(s):
            if c in '+-*':
                left = dp(s[:i])
                right = dp(s[i+1:])
                for l in left:
                    for r in right:
                        if c == '+':
                            res.append(l + r)
                        elif c == '-':
                            res.append(l - r)
                        else:
                            res.append(l * r)
        return res

    return dp(expression)

TimeO(n × 2^n)

SpaceO(2^n)

WHY IT WORKS

Divide and conquer with memoization. Split at each operator, compute all combinations of left and right results.

Open practice view →Open original problem ↗

10Check if a Parentheses String Can Be ValidMedium

Given parentheses string s and binary string locked. If locked[i]='0', can change s[i]. Return if s can be made valid.

pythonREFERENCE

def canBeValid(self, s: str, locked: str) -> bool:
    if len(s) % 2 == 1:
        return False

    def check(s, locked, open_char):
        balance = 0
        for i in range(len(s)):
            if s[i] == open_char or locked[i] == '0':
                balance += 1
            else:
                balance -= 1
            if balance < 0:
                return False
        return True

    return check(s, locked, '(') and check(s[::-1], locked[::-1], ')')

TimeO(n)

SpaceO(1)

WHY IT WORKS

Same greedy two-pass as Q678 wildcard validation. Unlocked positions (locked[i]='0') act as wildcards that can be either '(' or ')'.

Open practice view →Open original problem ↗

NEXT PATTERNArrays & Hashing→