Valid parentheses (multiple bracket types).

Problem. Given a string containing only ()[]{}, determine whether the brackets are balanced: every opener is closed by the matching closer, and pairs nest correctly. "([])" is valid; "([)]" and "(]" are not.

Brute force — O(n²) time

Repeatedly find an innermost matched pair ((), [], or {}) and delete it; if the string becomes empty it was valid. Each pass removes one pair and rescans, so it is O(n²). Correct but wasteful — and it quietly screams "use a stack."

Optimal — O(n) time, O(n) space

The matching rule is LIFO: the most recently opened bracket must be the first to close. That is exactly a stack. Push each opener; on a closer, the stack top must be its matching opener — otherwise fail fast. At the end the stack must be empty (no unclosed openers).

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(' -> stack.push(')');   // push the EXPECTED closer
            case '[' -> stack.push(']');
            case '{' -> stack.push('}');
            // c is a closer: it must equal what we expect on top
            default -> {
                if (stack.isEmpty() || stack.pop() != c) return false;
            }
        }
    }
    return stack.isEmpty();   // any leftover opener => unbalanced
}

Pushing the expected closer instead of the opener is a clean trick: the closer branch becomes a single equality check, no lookup table needed.