Valid Parentheses

Start from brute force

The obvious approach deletes matched pairs until nothing changes: repeat s = s.replace("()", "").replace("[]", "").replace("{}", "") and answer whether s ends up empty. It works because a valid string always contains an adjacent matched pair (its innermost one), and deleting that pair keeps a valid string valid and an invalid one invalid. Each pass is O(n) time and builds a new string, O(n) space. It is too slow on deep nesting: 5,000 ( followed by 5,000 ) exposes only the innermost pair per pass, so it takes 5,001 passes over a 10,000-character string, O(n²) time.

The approach

The bracket that may close next is always the most recently opened one that is still open, so the open brackets come back in last-in, first-out order: a stack. The invariant: after any prefix, stack holds exactly that prefix’s unmatched openers in the order they were opened, so its top is the only opener a closing bracket may match.

The reference maps each closer to its opener in pairs = {')': '(', ']': '[', '}': '{'}. For each ch, an opener (ch in pairs.values()) is pushed. A closer must find a non-empty stack whose popped top equals pairs[ch]: the single check if not stack or stack.pop() != pairs[ch] returns False for a stray closer, a wrong type and a wrong order alike, and short-circuiting means pop() never runs on an empty list. At the end, return not stack rejects anything still open, such as '(('.

Walk through an example

The fifth example, s = "{[]}", where nesting takes the stack two deep.

Complexity

Stack: O(n) time, one pass with constant work per character (the dict and pairs.values() checks cover three entries), and O(n) space in the worst case, when the string is all openers. Repeated pair removal: O(n²) time, up to about n/2 passes of O(n) each on nested input, and O(n) space for each rebuilt string.

Edge cases to test

• Only openers, "(((": false. Every character is pushed and nothing fails inside the loop; only the final return not stack catches it.
• A closer on an empty stack, ")(": false at the first character. In Python an unguarded stack.pop() raises IndexError; in TypeScript pop() returns undefined, which never equals an opener, so the reference returns false safely.
• Right counts, wrong order, "([)]": false. Each type has one opener and one closer, so a check with one counter per type accepts it; the stack sees ) arrive while [ is on top.
• Deep nesting, 5,000 ( then 5,000 ): true, with the stack 5,000 deep at its peak. A recursive matcher that recurses once per level passes Python’s default recursion limit of 1,000.
• Odd length, e.g. "(()": always false, which makes len(s) % 2 == 1 a valid early exit.
• The empty string: the reference returns True, since nothing is left open, although the constraints promise at least one character.

Common mistakes

• Not checking the stack is empty at the end, so "(((" is wrongly accepted.
• Popping an empty stack on a stray closing bracket — check emptiness first.
• Only counting brackets rather than matching types and order, so "([)]" slips through — it must fail.

Follow-ups an interviewer asks next

Return the position of the first error instead of a boolean.

Push indices instead of characters. A closer that meets an empty stack or a mismatched top is the error, so return its index. If the loop finishes with indices still on the stack, every one of them is an unclosed opener: report the innermost, stack[-1], or the outermost, stack[0], depending on what an editor should highlight.

The string also contains letters, digits, or real code.

Skip any character that is neither an opener nor a closer; the reference already does, because such a character fails both the if and the elif, so "a(b)c" is valid. Real code adds string literals and comments, where brackets do not count, so a real checker tracks lexer state, such as being inside a string, before it consults the stack.

Only one bracket type. Can you use O(1) space?

Yes. With a single type the stack only ever holds copies of (, so its height is all the information it carries: a counter that rises on ( and falls on ), failing if it ever goes below zero and requiring zero at the end. With two or more types the order of the types matters, and no fixed set of counters records it.

Generate every valid string of n pairs.

Backtrack with two counters: add ( while fewer than n have been opened, and add ) while closers trail openers. Every string completed at length 2n is valid by construction, so no check is needed. There are Catalan(n) of them, 42 for n = 5, so the size of the output, not the checking, dominates the cost.

Where this shows up

This is the canonical stack problem, and the “match nested pairs with a stack” pattern is exactly how parsers, expression evaluators, JSON/XML validators, and your editor’s bracket-matching work. Recognizing that “most recent unmatched open” means “stack” is the transferable insight.

Reference solution

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}   # closing -> matching opening
    stack = []
    for ch in s:
        if ch in pairs.values():             # an opening bracket
            stack.append(ch)
        elif ch in pairs:                    # a closing bracket
            # must match the most recent unmatched open
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack                         # valid only if nothing is left open


print(is_valid("()[]{}"))   # -> True
print(is_valid("([)]"))     # -> False

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  const opens = new Set(Object.values(pairs));
  const stack: string[] = [];
  for (const ch of s) {
    if (opens.has(ch)) {
      stack.push(ch);                 // opening: remember it
    } else if (ch in pairs) {
      // closing: top of stack must be the matching open
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;          // valid only if nothing is left open
}

console.log(isValid("()[]{}"));       // -> true
console.log(isValid("([)]"));         // -> false