Valid Parentheses

1. Problem & Core Objective

The problem

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

A string is valid when:

1. Open brackets are closed by the same type of bracket, and
2. Open brackets are closed in the correct order, and
3. Every close bracket has a corresponding open bracket of the same type.

Input:  s = "()"           Output: true
Input:  s = "()[]{}"       Output: true
Input:  s = "(]"           Output: false     (wrong type)
Input:  s = "([)]"         Output: false     (wrong order — interleaved)
Input:  s = "{[]}"         Output: true      (properly nested)

Constraints:

• 1 <= s.length <= 10^4
• s consists of parentheses only: ()[]{}

What the interviewer is actually testing

This is a two-minute problem. What's being assessed is whether you can justify the data structure and enumerate the failure modes.

1. Can you say why a stack? Not "because it's the bracket problem" — because a closing bracket must match the most recently opened one, and "most recent" is precisely what a stack gives you in O(1).
2. Do you name both failure modes? A closer arriving with nothing open, and openers left over at the end. Candidates routinely handle one and forget the other.
3. Do you see why counting doesn't work? Tracking a counter per bracket type gets "([)]" wrong — the counts balance but the order is invalid. That's the case that proves you need a stack rather than three counters.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^4. O(n) is trivially achievable and O(n²) would be 10^8 — passable but clearly not the intent.

The alphabet is exactly six characters, so no general parsing machinery is needed.

Step 2 — Try counting, and watch it fail

The naive idea: keep a counter per bracket type, increment on open, decrement on close, and check everything ends at zero with nothing going negative.

Test it on "([)]":

Counting says valid. It isn't — the brackets interleave rather than nest.

Counting captures how many are open, but not which one is innermost. That distinction is the entire problem.

Step 3 — What the problem actually requires

When a ) arrives, it must match the most recently opened, still-unclosed bracket. Nothing else can be its partner — anything opened earlier is enclosing it, and anything opened later would already have had to close.

So the question becomes: what structure returns the most recently added, still-unresolved item?

That's last-in-first-out. A stack.

Step 4 — The algorithm

• Opening bracket → push it; it is now the innermost unresolved bracket.
• Closing bracket → the top of the stack must be its matching opener. Pop and compare.

Step 5 — Enumerate the failure modes

Three ways a string can be invalid, and each needs a distinct check:

The third is the one people forget. A loop that never fails still leaves unmatched openers on the stack, and returning true there is wrong.

3. Solution Paths

Approach 1 — Repeatedly delete adjacent pairs

public boolean isValid(String s) {
    int prevLength = -1;
    while (s.length() != prevLength) {
        prevLength = s.length();
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
    }
    return s.isEmpty();
}

How it works. A valid string always contains at least one adjacent matched pair. Delete all of them, repeat, and a valid string eventually reduces to nothing.

• Time: O(n²) — each pass is O(n) and up to n/2 passes may be needed.
• Space: O(n) for the new strings.

Counter-questions on this approach

⭐ "Why does this need repeated passes rather than one?"

Because deleting an inner pair creates a new adjacent pair. "{[]}" → "{}" → "" takes three passes. Each pass only removes the currently-innermost layer, so nesting depth drives the pass count — which is what makes it O(n²) on deeply nested input like "((((…))))".

"String.replace allocates a new string each call. Does that matter?"

Yes — three allocations per pass, each O(n). On n = 10^4 with deep nesting that's real work for no benefit. It's a cute observation about the structure of valid strings, not a solution I'd offer as my answer.

Approach 2 — Stack with a map of pairs (optimal)

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

    for (char c : s.toCharArray()) {
        if (pairs.containsKey(c)) {                 // a CLOSING bracket
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
        } else {                                    // an OPENING bracket
            stack.push(c);
        }
    }
    return stack.isEmpty();                         // leftovers = invalid
}

Trace on "([)]":

Trace on "{[]}":

Empty at the end → true ✓

• Time: O(n) — one pass, O(1) per character.
• Space: O(n) — worst case all openers, e.g. "(((((".

Counter-questions on this approach

⭐ "Why a stack rather than three counters, one per bracket type?"

Counters track how many of each type are open, but not which one is innermost. On "([)]" the counts balance perfectly and it still isn't valid, because the brackets interleave rather than nest. A closing bracket must match the most recently opened one, and only a stack answers that.

⭐ "What happens if you drop the final stack.isEmpty() and just return true?"

"((" would return true. The loop never fails — there's no closing bracket to trigger a mismatch — but two openers are left unresolved. That's one of three distinct failure modes, and it's the one candidates most often miss.

"Why check stack.isEmpty() before popping?"

Because ArrayDeque.pop() throws NoSuchElementException on an empty deque. On input ")" the very first character would crash. The || short-circuits, so the check must come first.

"You key the map by closing bracket. Why that direction?"

It makes pairs.containsKey(c) the test for "is this a closer", which is the branch I need. Keying by opener would force a separate way to classify the character. Small design choice, but it removes a line.

"Space is O(n) — can it be reduced?"

Not in general. "((((…" genuinely requires remembering every opener, so O(n) is a real lower bound for the worst case. For a single bracket type you could use a counter at O(1) — which is exactly why the three-type version needs a stack.

Approach 3 — Push the expected closer

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(')      stack.push(')');        // push what we EXPECT to see
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

How it works. Instead of pushing the opener and translating on close, push the character you expect next. Then a closer is valid exactly when it equals the top — a direct comparison with no lookup.

• Time: O(n).
• Space: O(n).

Counter-questions on this approach

⭐ "Is this actually better than the map version, or just different?"

Marginally better and mostly stylistic: it removes the Map allocation and turns the match into a direct character comparison rather than a hash lookup. Both are O(n). I'd offer it as a neat variant — the map version generalizes more cleanly if the bracket set grew or came from configuration.

"The else branch assumes anything that isn't an opener is a closer. Is that safe?"

Only because the constraints guarantee the string contains nothing but those six characters. If arbitrary characters were possible, that else would treat a letter as a closing bracket and wrongly return false. I'd add an explicit closer check — and it's worth confirming the constraint rather than relying on it silently.

Comparison

4. Why the Optimal Wins

Against repeated deletion. That approach removes one nesting layer per pass, so deeply nested input needs O(n) passes of O(n) work. The stack handles arbitrary nesting depth in a single pass, because the stack itself is the record of the nesting.

Against counting. This is the more instructive comparison, and worth raising unprompted: counters are O(1) space and look attractive, but they discard ordering. "([)]" is the one-line disproof. Whenever a problem depends on which item is innermost rather than how many are open, counting is insufficient.

Why O(n) time is the floor. Every character must be examined — an adversary can place the mismatch anywhere, including the last position. So O(n) is optimal.

Why O(n) space is unavoidable. On "((((…" you must remember every unresolved opener, since any of them could be closed later. There's no compression available in the worst case.

The transferable idea:

When resolution must happen in reverse order of arrival — innermost first, most recent first — that's a stack.

That's the same shape as expression evaluation (Q3), function call frames, and undo history.

5. Java Prerequisites

ArrayDeque as a stack

Deque<Character> stack = new ArrayDeque<>();
stack.push(c);       // addFirst
stack.pop();         // removeFirst — THROWS NoSuchElementException if empty
stack.peek();        // peekFirst — returns null if empty
stack.isEmpty();

Use ArrayDeque, not java.util.Stack — the latter is a legacy synchronized Vector, and it iterates bottom-to-top, which is the reverse of what you'd expect. See 02 §5.

pop throws, poll returns null

stack.pop();         // throws on empty
stack.poll();        // returns null on empty

The solution guards with isEmpty() before popping. An alternative is poll() with a null check — either is fine, but don't mix the families within one method.

Map.of for small immutable maps

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

Java 9+, immutable, up to 10 key-value pairs. Convenient for fixed lookup tables. It rejects null keys and values, which is irrelevant here.

Character comparison

stack.pop() != pairs.get(c)

stack.pop() returns Character (boxed) and pairs.get(c) returns Character. This is != on two boxed objects — but it's safe here, because Java caches Character objects for values 0–127 and all six brackets are ASCII.

That's an accident of the constraints, not a guarantee. The unambiguous form is:

if (stack.isEmpty() || stack.pop().charValue() != pairs.get(c)) return false;

Worth knowing — the same trap with Integer above 127 is a genuine bug generator. See 03.

toCharArray vs charAt

for (char c : s.toCharArray())     // O(n) copy, cleaner to read
for (int i = 0; i < s.length(); i++) s.charAt(i);   // no allocation

Single sequential pass, so either is fine. toCharArray reads better here.

6. Interview Communication Guide

Clarifying questions

1. "Can the string contain characters other than the six brackets?" — the constraints say no, which justifies the else-is-a-closer shortcut.
2. "Is an empty string valid?" — conventionally yes; the constraints say n >= 1, so it can't occur, but confirming shows care.
3. "Do different bracket types need to nest, or just balance independently?" — they must nest. "([)]" is the case that decides this.
4. "Is the input guaranteed non-null?"
5. "Should I return a boolean, or the position of the first error?" — boolean here.

The pitch

"A closing bracket has to match the most recently opened bracket that's still unclosed — anything opened earlier is enclosing it. 'Most recent unresolved item' is exactly a stack.

So: push every opener. On a closer, the top of the stack must be its matching opener — pop and compare.

There are three ways to be invalid, and I want to handle all of them. A closer arriving with an empty stack. A closer of the wrong type. And openers left over at the end — that last one is easy to miss, since the loop completes without ever failing.

Worth noting why counters don't work: if I just tracked how many of each type were open, \"([)]\" would pass — the counts balance, but the brackets interleave instead of nesting. Counting loses the ordering, which is the entire problem.

O(n) time, O(n) space — and the space is unavoidable, since \"(((((\" genuinely requires remembering every opener."

Edge cases to raise proactively

"([)]" is the one to volunteer, and say why: it's the input that proves a stack is necessary rather than three counters. ")" and "((" together demonstrate you enumerated the failure modes rather than testing one.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "What's the minimum number of insertions/deletions to make the string valid?" (LC 921 / 1249)

Same single pass, but instead of returning false on a mismatch, count it. Keep a counter of unmatched closers encountered and, at the end, add the stack's remaining size for unmatched openers. The sum is the number of edits. Still O(n) time — and it only works because the stack already tells you exactly what's unresolved.

"What if * could be an open bracket, a close bracket, or empty?" (LC 678 — Valid Parenthesis String)

The stack breaks, because you can't decide what a * is at the moment you see it. Instead track a range of possible open counts, [lo, hi]: ( increments both, ) decrements both, * decrements lo and increments hi. Return false if hi goes negative, clamp lo at 0, and the string is valid if lo == 0 at the end. O(n) time, O(1) space. See 20 — Greedy.

"Remove the minimum number of parentheses to make it valid, and return the result." (LC 1249)

Push indices rather than characters, so the stack identifies exactly which positions are unmatched. Mark those for deletion, then rebuild the string skipping them. O(n) time and space. Storing indices instead of values is the recurring monotonic-stack habit.

"What if the string is enormous and streams in — you can't hold it in memory?"

The stack already works: it holds only unresolved openers, never the whole string. Memory is O(depth) rather than O(n). That the algorithm survives this untouched is a sign it's the right one.

"What if brackets came from configuration — an arbitrary set of pairs?"

The map version generalizes directly: build Map<Character,Character> from the configured pairs and the algorithm is unchanged. The expected-closer variant would need the same map to know what to push, so the map version is the better base for this.

"Validate a full expression — brackets plus operators and operands."

Bracket matching becomes one component of a proper parser. The stack is still the core, but you'd also track operator precedence — typically the shunting-yard algorithm, which uses two stacks. The output of that is exactly the RPN form evaluated in Evaluate Reverse Polish Notation.