Input: s = '([]{})'
Output: True

Input: s = '([]{)}'
Output: False

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

An early observation is that for each type of parenthesis, the number of opening and closing parenthesis must be identical. However, to check if an expression is valid, this observation alone isn’t enough. For example, the string "())(" has the same number of opening and closing parentheses, but is still invalid. This means we need a way to account for the order of parentheses.

Consider the string “()”. The first parenthesis is opening, and we’re waiting for it to be closing. Upon reaching the second parenthesis, the first parenthesis gets closed.

Now, consider the string “[(])”. When we reach index 1, we have two opening parentheses waiting to be closed. In particular, we expect ‘(‘ to be closed before ‘[’. The first closing parenthesis we encounter is ‘]’, which does not close ‘(’. Therefore, this string is invalid.

The key observation here is that the most recent opening parenthesis we encounter should be the first parenthesis that gets closed. So, opening parentheses are processed from most recent to least recent, which is indicative of a last-in-first-out (LIFO) dynamic. This leads to the idea that a stack can be used to solve this problem.

Stack
Here’s a high-level strategy:

• Add each opening parenthesis we encounter to the stack. This way, the most recent parenthesis is always at the top of the stack.

• When encountering a closing parenthesis, check if it can close the most recent opening parenthesis.

  • If it can, close that pair of parenthesis by popping off the top of the stack.
  • If not, the string is invalid.

Let’s see how this strategy works over an example:

For each opening parenthesis we encounter, push it to the top of the stack:

Next, we encounter a closing parenthesis. Comparing it to the opening parenthesis at the top of the stack, we see that it correctly closes that opening parenthesis. So, we can pop off the opening parenthesis at the top of the stack:

The next character is an opening parenthesis, which we just push to the top of the stack:

The next character is a closing parenthesis, ‘)’, which does not close the opening parenthesis at the top of the stack, ‘{’. This means this parenthesis expression is invalid. As such, we return false.

If we’ve iterated over the entire string without returning false, that means we’ve accounted for all closing parentheses in the string.

Edge case: extra opening parentheses
We only check for invalidity at closing parenthesis, so need to perform a final check to ensure there aren’t any opening parentheses in the string left unclosed. This can be done by checking if the stack is empty after processing the whole input string, as a non-empty stack indicates opening parentheses remain in the stack.

Managing three types of parentheses
In our algorithm, we need a way to ensure we compare the correct types of opening and closing parentheses. We can use a hash map for this, which maps each type of opening parenthesis to its corresponding closing parenthesis:

This hash map can also be used as a way to check if a parenthesis is an opening or a closing one: if the parenthesis exists in this hash map as a key, it’s an opening parenthesis.

Implementation

def valid_parenthesis_expression(s: str) -> bool:
    parentheses_map = {'(': ')', '{': '}', '[': ']'}
    stack = []
    for c in s:
        # If the current character is an opening parenthesis, push it onto the stack.
        if c in parentheses_map:
            stack.append(c)
        # If the current character is a closing parenthesis, check if it closes the
        # opening parenthesis at the top of the stack.
        else:
            if stack and parentheses_map[stack[-1]] == c:
                stack.pop()
            else:
                return False
    # If the stack is empty, all opening parentheses were successfully closed.
    return not stack

bool validParenthesisExpression(string s) {
    unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    vector<char> stack;
    for (char c : s) {
        if (pairs.count(c) > 0) {            // c is a closing bracket
            if (stack.empty()) {
                return false;
            }
            char top = stack.back();
            stack.pop_back();
            if (top != pairs[c]) {
                return false;
            }
        } else {                             // c is an opening bracket
            stack.push_back(c);
        }
    }
    return stack.empty();
}

public boolean validParenthesisExpression(String s) {
    Map<Character,Character> pairs = Map.of(')','(', ']','[', '}','{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (pairs.containsKey(c)) {          // c is a closing bracket
            if (stack.isEmpty()) return false;
            char top = stack.pop();          // primitive char -> compares by value
            if (top != pairs.get(c)) return false;
        } else {                             // c is an opening bracket
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

Complexity Analysis

Time complexity: The time complexity of valid_parenthesis_expression is $O(n)$ because we traverse the entire string once. For each character, we perform a constant-time operation, either pushing an opening parenthesis onto the stack or popping it off for a matching closing parenthesis.

Space complexity: The space complexity is $O(n)$ because the stack stores at most $n$ characters, and the hash map takes up $O(1)$ space.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language