Valid Parentheses

EASY✓ CHIP-TIMEDLC #20 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

EX 01

s = "()"

→ true

SIMPLEST VALID PAIR

EX 02

s = "()[]{}"

→ true

BACK-TO-BACK, ALL THREE TYPES

EX 03

s = "(]"

→ false

WRONG CLOSING TYPE

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

THE HINTS — TAKE 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 BOARD — THE 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 SPLITS — TWO 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-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED