Valid Parentheses

The briefingthe full drill, in my own words

The drill: Decide whether a string of round, square, and curly brackets closes correctly — every bracket must be closed by the same type, in the right order, with nothing left dangling.

A string made only of the six bracket characters — (), [], {} — arrives, and the job is to decide whether it's properly balanced.

Balanced means every opening bracket is eventually closed by a bracket of the exact same type, and the closing happens in the right nested order — the most recently opened bracket must be the next one closed.

A string counts as valid only when the entire input closes cleanly with nothing left open and nothing closed out of turn; anything else counts as invalid.

string length ranges from empty to several thousand characters
only the six characters ( ) [ ] { } ever appear
closing order must match the most recently opened bracket
answer is a single true or false verdict

EX 01

s = "()"

→ true

simplest valid pair

EX 02

s = "()[]{}"

→ true

back-to-back, all three types

EX 03

s = "(]"

→ false

wrong closing type

The hintstake only what you need

HINT 1 THE NUDGE

Only the most recently opened bracket can legally be the next one closed. Anything that respects that ordering is valid; anything that violates it isn't.

HINT 2 THE STRUCTURE

A stack is built for exactly this: last opened, first closed. Push every opening bracket you see.

HINT 3 ONE STEP FROM THE ANSWER

On a closing bracket, pop the stack and check it matches; a mismatch or an empty stack means invalid, and the string is valid only if the stack is empty once you've read it all.

Coach's boardthe pattern, step by step

STACK OF OPENSPATTERN · STACK MATCHINGs = "([{}])"

(

[

{

}

]

)

STACK OF OPENS

— empty —

STEP 1

Only three bracket shapes matter: push an open, and a close must match the top of the stack.

STEP 1 / 8 · ← → WORK TOO

The splitstwo paces, two languages

grind/valid-parentheses.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def isValid(self, s: str) -> bool:
        closer_to_opener = {")": "(", "]": "[", "}": "{"}
        stack = []
        for ch in s:
            if ch in closer_to_opener:
                if not stack or stack.pop() != closer_to_opener[ch]:
                    return False
            else:
                stack.append(ch)
        return not stack

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 11 LN

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {"()", "[]", "{}"}
        changed = True
        while changed:
            changed = False
            for i in range(len(s) - 1):
                if s[i:i + 2] in pairs:
                    s = s[:i] + s[i + 2:]
                    changed = True
                    break
        return s == ""

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 12 LN

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char open = stack.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 19 LN

class Solution {
    public boolean isValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i + 1 < sb.length(); i++) {
                char a = sb.charAt(i);
                char b = sb.charAt(i + 1);
                if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}')) {
                    sb.delete(i, i + 2);
                    changed = true;
                    break;
                }
            }
        }
        return sb.length() == 0;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED