Valid Parentheses

Valid Parentheses is a stack problem. Every closing bracket must match the most recent unmatched opening bracket.

The useful mental model: brackets close in reverse order. That is exactly what a stack gives us.

Problem

Given a string s containing bracket characters, return true if the string is valid.

A string is valid when:

• every opening bracket has a matching closing bracket
• brackets close in the correct order
• every closing bracket matches the latest open bracket

Examples:

"()" -> true
"()[]{}" -> true
"(]" -> false
"([)]" -> false
"{[]}" -> true

First Attempt

public boolean isValid(String s) {
    if (s == null && s.length() % 2 != 0) return false;

    Map m = Map.of(
            '}', '{',
            ')', '(',
            ']', '['
    );

    Deque<Character> st = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (m.containsKey(c)) {
            if (st.isEmpty() || st.pop() != m.get(c)) return false;
        } else {
            st.push(c);
        }
    }

    return st.isEmpty();
}

The stack idea is right. The map from closing bracket to opening bracket is also a clean move.

The important bug is in the guard:

if (s == null && s.length() % 2 != 0) return false;

This should be ||, not &&.

If s is null, then s.length() throws NullPointerException. We want to stop before calling length().

What Changed

Tune the solution in three places:

1. Use || in the null/odd-length guard.
2. Use generics: Map<Character, Character>.
3. Push only opening brackets, and reject unexpected characters if the input is not guaranteed to contain only brackets.

For the standard LeetCode version, the input contains only bracket characters, so the final else can push opening brackets directly.

Final Version

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() % 2 != 0) {
            return false;
        }

        Map<Character, Character> pairs = Map.of(
            ')', '(',
            ']', '[',
            '}', '{'
        );

        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }

        return stack.isEmpty();
    }
}

Walkthrough

Input:

s = "{[]}"

Steps:

At the end, the stack is empty, so the string is valid.

Why The Stack Works

Consider:

([)]

When we reach ), the most recent opening bracket is [, not (.

That means the string is invalid immediately. The stack lets us check the latest unmatched opening bracket in O(1).

Stricter Version

If the input may contain non-bracket characters, reject them:

if (pairs.containsKey(c)) {
    if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
        return false;
    }
} else if (c == '(' || c == '[' || c == '{') {
    stack.push(c);
} else {
    return false;
}

Complexity

The worst-case space happens when every character is an opening bracket.

Takeaways

• Use a stack when the latest unmatched item must close first.
• Map closing brackets to their expected opening brackets.
• Check s == null || s.length() % 2 != 0, not &&.
• Return false immediately when a closing bracket does not match the stack top.
• The string is valid only if the stack is empty at the end.