Solution: Matching with a Stack

Let’s make an observation: suppose we go over the string from left to right. When we find a closing bracket, it must match the most recently opened bracket that has not been closed yet. If I were to store the opening brackets in order, the most recent one would be the last one added, which is exactly the behavior of a stack: last in, first out.

Let’s turn this observation into an algorithm:

• Go over the string from left to right.
• On an opening bracket, push it onto the stack.
• On a closing bracket, the matching opener must be at the top of the stack.
• If the stack is empty, there is no opener for it, and the string is invalid.
• If the top is an opener of a different type, the string is invalid.
• Otherwise, pop the opener; that pair is matched.
• At the end of the string, if the stack is not empty, the string is invalid.

Let’s build this in code, starting with the boilerplate for traversing the string:

public static boolean isValid(String s) {
  Stack<Character> stack = new LinkedStack<>();  // or use ArrayStack

  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // process c here
  }

  return stack.isEmpty();
}

Now we process the character. If it is an opening bracket, we push it:

if (c == '(' || c == '[' || c == '{') {
  stack.push(c);
}

Otherwise, it is a closing bracket, and we apply the checks from the algorithm:

else {
  if (stack.isEmpty()) {
    return false;  // a closing bracket with no opener
  }
  char open = stack.top();
  stack.pop();
  if (!matches(open, c)) {
    return false;  // closed by the wrong type
  }
}

Remember that our pop does not return the removed item; that is why we call top to read the opener and then pop to remove it. The matches check goes in a small helper:

private static boolean matches(char open, char close) {
  return (open == '(' && close == ')')
      || (open == '[' && close == ']')
      || (open == '{' && close == '}');
}

Here is the complete implementation:

public static boolean isValid(String s) {
  Stack<Character> stack = new LinkedStack<>();

  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);

    if (c == '(' || c == '[' || c == '{') {
      stack.push(c);
    } else {
      if (stack.isEmpty()) {
        return false;  // a closing bracket with no opener
      }
      char open = stack.top();
      stack.pop();
      if (!matches(open, c)) {
        return false;  // closed by the wrong type
      }
    }
  }

  return stack.isEmpty();
}

Let’s trace it on ([)]. The first character ( is an opener, so we push it:

┌───┐
│ ( │ ◀── top
└───┘

The next character [ is also an opener; push it as well:

┌───┐
│ [ │ ◀── top
├───┤
│ ( │
└───┘

The third character ) is a closer, so we check the stack. The top is [, which is not its opener: matches fails and the method returns false.

Now {[()]}. The first three characters are all openers. Push {:

┌───┐
│ { │ ◀── top
└───┘

then [:

┌───┐
│ [ │ ◀── top
├───┤
│ { │
└───┘

then (:

┌───┐
│ ( │ ◀── top
├───┤
│ [ │
├───┤
│ { │
└───┘

The rest of the characters are closers, and they come in the reverse order of their openers. ) matches the ( on top and pops it:

┌───┐
│ [ │ ◀── top
├───┤
│ { │
└───┘

] matches the [ and pops it:

┌───┐
│ { │ ◀── top
└───┘

and } matches the { and pops it:

(empty stack — every bracket matched)

The loop ends with an empty stack, so the method returns true.

An empty string skips the loop and returns true, since the stack starts empty. The string )( fails at the first character: it is a closer and the stack is empty. The string (() pushes more than it pops, so the stack is not empty at the end, and the method returns false.

Finally, the complexity. We make one pass over the string. Each character is pushed at most once and popped at most once, and every stack operation we call is $O(1)$, with push amortized on ArrayStack. So the runtime is $O(n)$. The auxiliary space is the stack itself, which in the worst case (a string of all openers) holds $n$ characters: $O(n)$.