Stack for Parentheses Matching

Before we start

The parentheses-matching stack is probably the first real stack problem you will encounter in interviews. It looks trivial at first, but the same core idea extends to five different problem variants — from "is this string valid?" all the way to "what is the score of this expression?" By the end you will be able to:

• Write the basic validity check from memory in under 30 seconds.
• Adapt the core stack to solve minimum-removal, longest-valid-substring, and score variants.
• Explain why a stack is the exact right data structure here (not a counter).

Picture this first (no code yet)

The actual problem

Valid Parentheses (LC #20):

Given a string containing only (, ), [, ], {, }, determine if it is valid. A string is valid if: every opener has a matching closer of the same type, and they close in the correct order.

"()[]{}" → true. "([)]" → false. "{[]}" → true. "]" → false.

First, the slow way (so you feel the pain)

The naive idea: repeatedly scan the string and remove adjacent matching pairs (), [], {} until no more can be removed. If the string becomes empty, it's valid. For "(((...)))" with 10,000 pairs, each removal shrinks the string by 2 — you scan 10,000 times with up to 20,000 characters each = 2 × 10⁸ character reads. The stack does it in exactly n reads.

The turning point

The one idea to remember

The code

def isValid(s: str) -> bool:
    stack = []
    match = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            # closer: stack must be non-empty AND top must match
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()

    return len(stack) == 0

Line-by-line narration:

1. stack = [] — our stack of unmatched openers.
2. match = {')': '(', ']': '[', '}': '{'} — maps each closer to its required opener.
3. if ch in '([{' — opener: push it.
4. if not stack — hitting a closer when the stack is empty means no opener waiting — invalid.
5. stack[-1] != match[ch] — the most recent opener doesn't match this closer — invalid.
6. stack.pop() — valid pair found; remove the opener.
7. return len(stack) == 0 — if unmatched openers remain, invalid.

Watch it happen, frame by frame

s = "{[()]}"

ch='{': opener → push.  stack=['{']
ch='[': opener → push.  stack=['{','[']
ch='(': opener → push.  stack=['{','[','(']
ch=')': closer. top='(' == match[')']='(' ✅ pop. stack=['{','[']
ch=']': closer. top='[' == match[']']='[' ✅ pop. stack=['{']
ch='}': closer. top='{' == match['}']='{' ✅ pop. stack=[]

Loop ends. len(stack)==0 → True  ✅

s = "([)]" — the tricky one

ch='(': push. stack=['(']
ch='[': push. stack=['(','[']
ch=')': closer. top='[' ≠ match[')']='(' → return False  ✅

Extension 1: Minimum Remove to Make Valid (LC #1249)

Given a string with letters and parentheses, remove the minimum number of brackets to make it valid.

Approach: collect indices of unmatched brackets (not characters, not counts — indices):

def minRemoveToMakeValid(s: str) -> str:
    s    = list(s)
    stack = []  # stores indices of unmatched '('

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()    # matched — good
            else:
                s[i] = ''      # unmatched ')' — remove immediately

    # anything left in stack is unmatched '('
    for i in stack:
        s[i] = ''

    return ''.join(s)

Why store indices? Because we need to mark which ( to remove — specifically the unmatched ones (the ones still in the stack after the full scan).

Extension 2: Longest Valid Parentheses (LC #32)

Find the length of the longest valid parenthesis substring.

Stack approach: store indices. Initialize stack with sentinel [-1] (the "before the string" boundary):

def longestValidParentheses(s: str) -> int:
    stack  = [-1]   # sentinel
    result = 0

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:   # ')'
            stack.pop()
            if not stack:
                stack.append(i)   # new boundary: this unmatched ')' index
            else:
                result = max(result, i - stack[-1])

    return result

The sentinel (or the most recent unmatched ) index) marks the "left boundary" of the current valid window. The length of the current valid window is i - stack[-1].

Extension 3: Score of Parentheses (LC #856)

Each () scores 1. Nested (A) scores 2×score(A). Adjacent AB scores score(A)+score(B).

def scoreOfParentheses(s: str) -> int:
    stack = [0]   # current layer's score

    for ch in s:
        if ch == '(':
            stack.append(0)   # open new layer
        else:
            val = stack.pop()
            stack[-1] += max(2 * val, 1)   # () → 1; (A) → 2*A

    return stack[0]

stack holds the running score of the current nesting level. On (, push 0 (new level). On ), pop the completed level's score: if 0 (was ()), add 1; otherwise add 2× (was nested).

Common traps

stack = []
match = {')': '(', ']': '[', '}': '{'}
for ch in s:
    if ch in '([{':
        stack.append(ch)
    elif not stack or stack[-1] != match[ch]:
        return False
    else:
        stack.pop()
return not stack

Check yourself

Practice problems

Next up: Min/Max Stack — augment a standard stack with an auxiliary stack so that getMin() and getMax() run in O(1) time, regardless of push/pop order.