Marauder Bot

Problem

A string contains only the six bracket characters: parentheses, square brackets, and curly braces. Determine whether the brackets are properly matched and nested, meaning every opening bracket has a corresponding closing bracket of the same type, and closing brackets appear in the correct order relative to the ones they close.

Example. {[()]} is valid, but ([)] is not, because the square bracket closes before the parenthesis that opened after it.

Key idea

A naive approach might repeatedly search for and remove adjacent matching pairs like () until nothing changes, but that means rescanning the string over and over. The better approach recognizes that brackets nest in last-in-first-out order: the most recently opened bracket must be the next one closed. That is exactly the behavior of a stack.

Walk the string once, pushing each opening bracket onto a stack. Each closing bracket must match whatever sits on top of the stack: if the stack is empty, or the top does not match the expected type, the string is invalid immediately. Otherwise pop the match and continue. After the last character, the string is valid only if the stack is empty, meaning every opener eventually found its closer.

Solution

function isValid(s: string): boolean {
  // Map each closing bracket to the opener it must match.
  const closingToOpening: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{',
  };
  const stack: string[] = [];

  for (const char of s) {
    if (char in closingToOpening) {
      // Invalid if there's nothing to close, or the top doesn't match.
      if (stack.length === 0 || stack[stack.length - 1] !== closingToOpening[char]) {
        return false;
      }
      stack.pop();
    } else {
      stack.push(char);
    }
  }

  // Empty stack means every opener found its closer.
  return stack.length === 0;
}

Complexity

Time: O(n). A single pass over the string with constant-time stack operations.
Space: O(n). The stack can hold up to half the characters if the string is all openers.

Watch out for

Attempting to pop from an empty stack when a closing bracket appears means the string is invalid; check for this before reading the top.
A non-empty stack at the end means some opening bracket was never closed.
Map each closing bracket to its expected opening type up front so the comparison is a simple lookup.

Pattern

This is the standard use of a stack for matching nested structures in last-in-first-out order. The same idea underlies parsing arithmetic expressions and validating XML or HTML tag nesting.

Valid Parentheses