Parentheses Problems

Before we start

Parentheses problems look deceptively simple — "is this balanced?" — until the interviewer asks for the longest valid substring, or the minimum brackets to remove, or the score. By the end of this chapter you will be able to:

• Solve the simple validity check in one pass with a counter — no stack needed.
• Find the longest valid parentheses substring in O(n) time two different ways.
• Recognise the three major variants and pick the right tool for each.

Picture this first (no code yet)

The moment the count goes negative — say you see )( — an exit with nobody on stage — the sequence is already invalid, no matter what comes after.

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

Brute force: for each possible substring, check if it is a valid parentheses sequence. For n = 10 000, there are ~50 million substrings. Checking each takes up to O(n) time. Total: O(n³). For n = 30 000 (a typical LeetCode constraint) that is 27 trillion operations. A single step takes a nanosecond — 27 trillion steps take 27 000 seconds. Nine hours. We need something drastically faster.

The turning point

"(())"   →   1, 2, 1, 0   — counter rises to 2, then falls back smoothly
"()()"   →   1, 0, 1, 0   — counter touches 0 twice in the middle

Both end at 0, both are valid. The difference: "(())" has one long valid block;
"()()" has two shorter valid blocks joined. This matters for "longest valid substring."

The one idea to remember

Problem 1 — Valid Parentheses (LC #20)

The counter approach works perfectly for a single bracket type. For multiple bracket types ((), [], {}), you need a stack to remember which type is open.

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

    for ch in s:
        if ch in '([{':
            stack.append(ch)           # push opener
        else:
            if not stack or stack[-1] != matching[ch]:
                return False           # no matching opener, or wrong type
            stack.pop()                # match found — both dissolve

    return len(stack) == 0             # all openers must have been matched

Frame-by-frame: "([)]"

ch='(' → stack = ['(']
ch='[' → stack = ['(', '[']
ch=')' → matching[')']='(' but stack[-1]='[' → mismatch → return False  ✅

Frame-by-frame: "()[]{}"

'(' → ['(']
')' → stack[-1]='(' == matching[')'] → pop → []
'[' → ['[']
']' → match → []
'{' → ['{']
'}' → match → []
stack empty → True  ✅

Problem 2 — Longest Valid Parentheses (LC #32)

This is the hard variant. Return the length of the longest substring that is a valid parentheses sequence.

Approach A: Stack of indices

Instead of storing characters, store indices on the stack. The stack always holds the index of the last unmatched character — the "boundary" before any valid sequence.

def longestValidParentheses(s: str) -> int:
    stack = [-1]    # -1 is the boundary before the string starts
    best  = 0

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)           # push index of opener
        else:
            stack.pop()               # try to match with the top
            if not stack:
                stack.append(i)       # no match — i becomes the new boundary
            else:
                best = max(best, i - stack[-1])  # length = current - last boundary

    return best

Frame-by-frame: "(()" (expect answer 2 — the inner "()")

stack = [-1]

i=0 '(': push 0.   stack = [-1, 0]
i=1 '(': push 1.   stack = [-1, 0, 1]
i=2 ')': pop 1.    stack = [-1, 0]   non-empty → best = max(0, 2-0) = 2
i=3 ')': pop 0.    stack = [-1]      non-empty → best = max(2, 3-(-1)) = 4

Wait — "(()" has length 3, and the answer should be 2 for "()" inside it. Let me re-trace the string.

Let me trace "(()" carefully:

s = "(()"   (length 3)
stack = [-1]

i=0 ch='(': stack = [-1, 0]
i=1 ch='(': stack = [-1, 0, 1]
i=2 ch=')': pop → 1 removed. stack = [-1, 0]. Non-empty.
            best = max(0, 2 - 0) = 2.

Answer: 2  ✅  (the valid part is s[1..2] = "()")

Frame-by-frame: ")()())"

stack = [-1]

i=0 ')': pop -1. Stack empty → push 0 (new boundary). stack=[0]
i=1 '(': push 1. stack=[0,1]
i=2 ')': pop 1. stack=[0]. best = max(0, 2-0) = 2.
i=3 '(': push 3. stack=[0,3]
i=4 ')': pop 3. stack=[0]. best = max(2, 4-0) = 4.
i=5 ')': pop 0. Stack empty → push 5 (new boundary). stack=[5]

Answer: 4  ✅  (the valid part is s[1..4] = "()()")

Approach B: Counter (two passes, O(1) space)

Scan left-to-right counting opens and closes. When they equalise, record the length. When closes exceed opens, reset both counters (invalid). Then scan right-to-left with reversed roles (catches cases where opens exceed closes at the end).

def longestValidParentheses_twopass(s: str) -> int:
    def scan(seq, open_ch, close_ch):
        opens = closes = best = 0
        for ch in seq:
            if ch == open_ch:   opens  += 1
            else:               closes += 1
            if opens == closes:
                best = max(best, 2 * closes)
            elif closes > opens:
                opens = closes = 0   # reset — invalid prefix
        return best

    return max(scan(s, '(', ')'), scan(reversed(s), ')', '('))

Two passes, O(n) time, O(1) space — no stack at all.

Problem 3 — Minimum Removes to Make Valid (LC #1249)

Find the minimum number of brackets to remove so the remaining string is valid.

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

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()    # matched — both stay
            else:
                remove.add(i)  # unmatched ')' — mark for removal

    # remaining items in stack are unmatched '('
    remove |= set(stack)

    return "".join(ch for i, ch in enumerate(s) if i not in remove)

After the loop: stack holds indices of ( that never found a match; remove holds indices of ) that had nothing to match against. Remove them all.

Problem 4 — Score of Parentheses (LC #856)

Score rules: () = 1, (A) = 2 × score(A), AB = score(A) + score(B).

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

    for ch in s:
        if ch == '(':
            stack.append(0)          # open new depth level
        else:
            v = stack.pop()          # score of what was inside
            stack[-1] += max(2 * v, 1)   # "()" scores 1; "(A)" scores 2*A

    return stack[0]

Frame-by-frame: "(()(()))"

stack=[0]
'(' → [0, 0]
'(' → [0, 0, 0]
')' → pop 0. max(2*0,1)=1. stack=[0, 1]
'(' → [0, 1, 0]
'(' → [0, 1, 0, 0]
')' → pop 0 → 1. stack=[0, 1, 1]
')' → pop 1 → max(2,1)=2. stack=[0, 3]
')' → pop 3 → max(6,1)=6. stack=[6]

Answer: 6  ✅

The toolkit summary

Common traps

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

Check yourself

Practice problems

Next up: String Building / Simulation — how to build a result string step by step when decoding nested structures (like "3[a2[bc]]") or evaluating expressions with a stack.