Valid Parentheses

Problem

You get a string made up only of the six bracket characters: (, ), {, }, [, ]. Decide whether the string is balanced: every opening bracket must be closed by a closing bracket of the same type, and brackets must close in the reverse order they were opened (the most recently opened bracket is always the first one closed). An empty stack of unfinished brackets at the end means the string is valid.

Return True if the string is balanced, False otherwise.

Examples

• "()[]{}" → True — three independent pairs, each opened and immediately closed.
• "([{}])" → True — pairs nest properly: the innermost {} closes first, then [], then ().
• "(]" → False — the closer ] does not match the most recent opener (.
• "((" → False — two openers are never closed.

Constraints

• 1 <= s.length <= 10^4
• s consists only of the characters ()[]{}

The length bound means a repeated-rescanning solution (O(n^2)) is already shaky; the expected solution is a single O(n) pass.

Think about it first

TL;DR

One-pass stack of unmatched openers — O(n) time, O(n) space.

Approach 1 — Brute force

A balanced string always contains at least one literal adjacent pair ((), [], or {}). Delete such pairs repeatedly; a valid string shrinks to empty, an invalid one gets stuck.

class Solution:
    def isValid(self, s: str) -> bool:
        changed = True
        while changed:
            changed = False
            for pair in ("()", "[]", "{}"):
                if pair in s:
                    s = s.replace(pair, "")
                    changed = True
        return s == ""

Complexity: O(n^2) time (each sweep is O(n) and may remove only one pair; up to n/2 sweeps), O(n) space for the rebuilt strings.

Why the constraints kill it: with n = 10^4 a deeply nested string like ((((...)))) forces ~5,000 full-string rescans and rebuilds — roughly 10^7–10^8 character operations, needlessly slow when one pass suffices.

Approach 2 — Stack

The insight: validity is a nesting property. At any point in the scan, the only closer that can legally appear is the one matching the most recently opened, not-yet-closed bracket. A stack stores exactly that: the sequence of still-open brackets, most recent on top. So push openers, and on every closer pop once and compare types.

class Solution:
    def isValid(self, s: str) -> bool:
        match = {")": "(", "]": "[", "}": "{"}
        stack: list[str] = []
        for ch in s:
            if ch in match:            # ch is a closer
                if not stack or stack.pop() != match[ch]:
                    return False
            else:                      # ch is an opener
                stack.append(ch)
        return not stack               # leftovers mean unclosed openers

Walkthrough on "([{}])":

Stack is empty at the end → True. On "(]": push (, then ] pops ( which does not match [ → False immediately.

Complexity: O(n) time — each character is pushed and popped at most once. O(n) space for the stack (worst case all openers).

Common pitfalls

• Popping an empty stack: input like "]" starts with a closer; guard with if not stack before popping or you get an exception (or a wrong answer).
• Forgetting the final emptiness check: "((" never triggers a mismatch — you must return not stack, not True, at the end.
• Matching only counts, not types: counting opens minus closes accepts "([)]"; the stack comparison of types is what rejects interleaved pairs.
• Early exit: if len(s) is odd you can return False immediately — a micro-optimization, but don’t let it replace the real checks.

Pattern takeaway

When a problem says “the most recent unfinished thing must be resolved first,” reach for a stack: push work as it opens, pop and validate as it closes, and treat a non-empty stack at the end as unfinished business. This exact push-opener/pop-on-closer skeleton reappears in expression parsing, HTML tag matching, and Decode String.