21.Valid Parentheses

EasyBlind 75Stack · 1/7

Problem

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', decide whether it is valid:

Every open bracket is closed by a bracket of the same type.
Open brackets are closed in the correct order (the most recently opened must close first).
Every close bracket has a matching open bracket.

Examples

Input:  s = "()[]{}"
Output: true

Input:  s = "([)]"
Output: false
Explanation: '[' is opened after '(' so it must close first, but ')' arrives first.

Input:  s = "{[]}"
Output: true
Explanation: Brackets are properly nested.

Constraints

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

💡 Key Insight

"The most recently opened bracket must be closed first" is exactly last-in, first-out. Push each opening bracket onto a stack; each closing bracket must match the top of the stack. The string is valid iff every closer matches and the stack is empty at the end.

Brute Force (Repeated Removal)

TimeO(n²)SpaceO(n)

Intuition

In any valid string, at least one adjacent pair "()", "[]" or "{}" exists (the innermost pair). Removing it leaves another valid string. So keep deleting adjacent pairs until nothing changes; the string was valid iff it becomes empty.

Algorithm

Repeat:
- Replace every "()", "[]", "{}" with "".
- If the length did not change, stop.
Return s.isEmpty().

Visualization

"{[()]}"  → remove "()" → "{[]}"
"{[]}"    → remove "[]" → "{}"
"{}"      → remove "{}" → ""      → true

"([)]"    → no adjacent pair      → stuck, not empty → false

Code

java

class Solution {
    public boolean isValid(String s) {
        int before;
        do {
            before = s.length();
            // strip every innermost matching pair
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (s.length() != before);
        return s.isEmpty();
    }
}

Complexity

Time: O(n²) — up to n / 2 rounds, each rebuilding a string of length up to n.
Space: O(n) — new strings are created on every replace.

Stack + Closer-to-Opener Map

TimeO(n)SpaceO(n)

Intuition

Scan left to right. Opening brackets are "pending" — push them. When a closing bracket appears, it must close the most recent pending opener, which is the top of the stack. A map from each closer to its opener makes the comparison simple.

Algorithm

Map ')' → '(', ']' → '[', '}' → '{'.
For each c in s:
- If c is a closer: if the stack is empty or pop() != map.get(c), return false.
- Otherwise push c.
Return stack.isEmpty().

Dry Run

s = "{[]}"

'{' push       stack: {
'[' push       stack: { [
']' pop '[' ✓  stack: {
'}' pop '{' ✓  stack: (empty) → true

Code

java

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

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> openerOf = new HashMap<>();
        openerOf.put(')', '(');
        openerOf.put(']', '[');
        openerOf.put('}', '{');

        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (openerOf.containsKey(c)) {
                // closer must match the most recent unmatched opener
                if (stack.isEmpty()) {
                    return false; // closer with nothing to close
                }
                char top = stack.pop(); // unbox before comparing
                if (top != openerOf.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty(); // leftover openers are unclosed
    }
}

Complexity

Time: O(n) — each character is pushed/popped at most once.
Space: O(n) — e.g. "((((((" pushes every character.

Stack of Expected ClosersOptimal

TimeO(n)SpaceO(n)

Intuition

Flip the bookkeeping: when we see an opener, push the closer we expect later. Then a closing bracket is correct iff it equals the popped value — no map, no branching on bracket type. A char[] used as a stack avoids boxing, and an odd-length string can be rejected immediately.

Algorithm

If n is odd, return false.
stack = new char[n], top = 0.
For each c:
- '(' → push ')'; '[' → push ']'; '{' → push '}'.
- Otherwise (a closer): if top == 0 or stack[--top] != c, return false.
Return top == 0.

Dry Run

flowchart TD
    A["s = '([)]'"] --> B["'(' → push ')'<br/>stack: )"]
    B --> C["'[' → push ']'<br/>stack: ) ]"]
    C --> D["')' → pop ']'"]
    D --> E{"']' == ')'?"}
    E -->|"no"| F["return false"]

Code

java

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false; // brackets come in pairs
        }
        char[] stack = new char[n];
        int top = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack[top++] = ')'; // remember which closer we now expect
            } else if (c == '[') {
                stack[top++] = ']';
            } else if (c == '{') {
                stack[top++] = '}';
            } else if (top == 0 || stack[--top] != c) {
                return false; // unexpected closer
            }
        }
        return top == 0;
    }
}

Complexity

Time: O(n) — one pass with O(1) work per character.
Space: O(n) — the stack array.

Complexity Comparison

Approach	Time	Space
Brute Force (repeated removal)	O(n²)	O(n)
Stack + Map	O(n)	O(n)
Stack of Expected Closers	O(n)	O(n)

Common Pitfalls

Counting brackets per type — "([)]" has balanced counts but invalid order; you need a stack.
Popping from an empty stack on a leading closer like ")(" — check emptiness first.
Returning true at the end without checking the stack is empty — "((" would wrongly pass.
Comparing two Character objects with ==/!= — that compares references; unbox one side to char first.
Using java.util.Stack — it works but is synchronized and slower; prefer ArrayDeque or a plain array.