Valid Parentheses

The problem

The string s contains only round, square and curly brackets: ( ) [ ] { }. Return true if the string is valid and false if it is not. Valid means three things. Every opening bracket is closed later by a closing bracket of the same kind. Every closing bracket closes a bracket that was opened before it. And a pair may sit inside another pair, as in "([])", or after it, as in "()[]", but never partly inside it, as in "([)]". An empty string is valid.

What to write

function solve(s: string): boolean

Input
s = "()[]{}"

Output
true

Input
s = "([)]"

Output
false

Constraints

0–10,000 bracket characters: (), [], {}.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The string holds nothing but brackets, so every character either opens something or closes something. Counting the brackets of each kind is not enough to judge it: in "([)]" every opening bracket has a closing bracket of its kind, and the string is still not valid.

2. Hint 2: Ask a smaller question

   You have read "{[(" and the next character is a closing bracket. Which one of the three open brackets is it allowed to close? What should happen to that bracket once it has been closed?

3. Hint 3: Name the pattern

   A closing bracket always belongs to the most recent opening bracket that is still open. So if you keep the open brackets in a list, you add at its end and remove from that same end. That is a last-in, first-out stack: "push" puts an item on top, and "pop" takes the top item off. Read the lesson on last-in, first-out stack.

4. Hint 4: State the invariant

   The stack holds exactly the opening brackets that are still open, oldest at the bottom and newest on top. A closing bracket is allowed only when its partner is on top, and then that partner leaves the stack.

5. Hint 5: Sketch the pseudocode

   Start with an empty stack. For each character: if it is an opening bracket, push it. Otherwise, if the stack is empty, return false; if not, pop the top and return false unless it is this bracket's partner. After the last character, return true only if the stack is empty.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Push opening brackets onto a stack. Each closing bracket must match the most recent opening bracket, and the stack must be empty at the end.

The slow way

Find a matching pair that stands side by side, such as "()", delete it, and repeat until no such pair is left. The string is valid if nothing remains. It is correct, but every round reads the string again: 10,000 brackets nested inside each other take 5,000 rounds, and reading the string once in each round adds up to about 25 million characters.

The insight

When a closing bracket arrives, only one earlier bracket matters: the most recent opening bracket that is still open. Everything opened before it has to wait until it is closed. So you never search the string. You only look at, and remove, the newest open bracket.

Step by step

1. Keep a stack of the opening brackets that are not closed yet. A stack is a list you only add to (push) and remove from (pop) at one end, the top. That hands you the newest open bracket in one step.
2. Know which opening bracket each closing bracket needs. A small table from each closing bracket to its partner turns "do these two match?" into one lookup, whichever of the three kinds it is.
3. An opening bracket goes on top of the stack to wait. You cannot judge an opening bracket when you meet it. Whether it is closed correctly only shows later, so it is stored until its closing bracket arrives.
4. A closing bracket must match the top of the stack, which it removes. The top is the newest bracket still open, the only one this bracket may close. A different bracket there, or an empty stack, means the string is not valid.
5. The string is valid only if no bracket is left open. No closing bracket was wrong, but an opening bracket may still be waiting, as in "(". An empty stack means every bracket found its partner.

The same numbered steps are the comments in each solution.

function solve(s) {
  // 1. Keep a stack of the opening brackets that are not closed yet
  const stack = [];
  // 2. Know which opening bracket each closing bracket needs
  const pairs = { ")": "(", "]": "[", "}": "{" };
  for (const c of s) {
    // 3. An opening bracket goes on top of the stack to wait
    if ("([{".includes(c)) stack.push(c);
    // 4. A closing bracket must match the top of the stack, which it removes
    else if (stack.pop() !== pairs[c]) return false;
  }
  // 5. The string is valid only if no bracket is left open
  return stack.length === 0;
}

function solve(s: string): boolean {
  // 1. Keep a stack of the opening brackets that are not closed yet
  const stack = [];
  // 2. Know which opening bracket each closing bracket needs
  const pairs: Record<string, string> = {
    ")": "(",
    "]": "[",
    "}": "{",
  };
  for (const c of s) {
    // 3. An opening bracket goes on top of the stack to wait
    if ("([{".includes(c)) stack.push(c);
    // 4. A closing bracket must match the top of the stack, which it removes
    else if (stack.pop()! !== pairs[c]) return false;
  }
  // 5. The string is valid only if no bracket is left open
  return stack.length === 0;
}

def solve(s):
    # 1. Keep a stack of the opening brackets that are not closed yet
    stack = []
    # 2. Know which opening bracket each closing bracket needs
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in s:
        # 3. An opening bracket goes on top of the stack to wait
        if char in "([{":
            stack.append(char)
        # 4. A closing bracket must match the top of the stack, which it removes
        elif not stack or stack.pop() != pairs[char]:
            return False
    # 5. The string is valid only if no bracket is left open
    return not stack

Example 2, traced

Input
s = "([)]"

Output
false

Why it works

The stack always holds the brackets that are still open, in the order they were opened. A pair may not sit partly inside another, so the newest open bracket has to be closed before any older one. The method checks exactly that at every closing bracket, and the last test makes sure nothing stays open.

Time and space

Time O(n), extra space O(n). Each character is handled once: it is pushed, or it is compared with one popped bracket. Both take one step, so the time is O(n) for n characters. A string made only of opening brackets puts all of them on the stack, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Counting the open brackets of each kind is not enough. In "([)]" both counts go up and come back to zero, and the string is still not valid: counts forget the order in which the brackets were opened.
• Test the stack at the end. Without that, "(" is accepted: no closing bracket was ever wrong, but one bracket was never closed.
• A closing bracket can arrive when nothing is open, as in "](". That string is not valid. In Python, popping an empty list is an error, so check for an empty stack first.

Pattern

Last-in, first-out stack.

Keep going