Valid Parentheses Solution

Problem

Given a string containing only the characters (, ), {, }, [, and ], determine if the input string is valid. A string is valid if every opening bracket is closed by the same type of bracket, in the correct order.

Example:

Input: s = "()[]{}" → Output: true
Input: s = "(]" → Output: false
Input: s = "([)]" → Output: false (wrong order)

Intuition

The problem asks whether every opening bracket is closed by the correct type in the correct order. The key insight is that the most recently opened bracket must be the first one closed — that's last-in, first-out, which is exactly what a stack gives you.

Approach 1 — Brute Force (Repeated Removal)

Repeatedly remove adjacent matching pairs ((), [], {}) until none remain. If the string is empty, it was valid.

Steps:

Loop until no replacements happen in a full pass
Each pass: replace (), [], {} with an empty string
If the string is empty at the end, return true

1def isValid(s: str) -> bool:
2    previous_length = -1
3    while len(s) != previous_length:
4        previous_length = len(s)
5        # Remove all adjacent matching pairs in one pass
6        s = s.replace("()", "").replace("[]", "").replace("{}", "")
7    return len(s) == 0

Time: O(n²) — each pass is O(n) and we may need up to n/2 passes
Space: O(n) — string replacement creates new strings

Approach 2 — Stack (Optimal)

Use a stack to track unmatched opening brackets. When we see a closing bracket, check that it matches the top of the stack.

Steps:

Build a map of closing bracket → its expected matching opener
For each character in the string:
- If it's an opening bracket, push it onto the stack
- If it's a closing bracket, check the stack isn't empty and the top matches
- If either check fails, return false
After the loop, return true only if the stack is empty

1def isValid(s: str) -> bool:
2    matching_opener = {")": "(", "]": "[", "}": "{"}
3    stack = []
4
5    for char in s:
6        if char in matching_opener:
7            # Closing bracket — check for a matching opener on top
8            if not stack or stack[-1] != matching_opener[char]:
9                return False
10            stack.pop()
11        else:
12            # Opening bracket — save it for later matching
13            stack.append(char)
14
15    # Valid only if every opener was matched and popped
16    return len(stack) == 0

Time: O(n) — single pass through the string
Space: O(n) — stack holds at most n/2 opening brackets

Complexity Summary

Approach	Time	Space	When to use
Brute Force (repeated removal)	O(n²)	O(n)	Never in production; useful as a first-instinct answer
Stack	O(n)	O(n)	Always — this is the standard solution

Common Mistakes

Not checking if the stack is empty before popping: if you see ] on an empty stack, you must return false immediately. The not stack guard handles this.
Forgetting to check the stack is empty at the end: "(((" passes every loop iteration without returning false, but leaves 3 unmatched openers. The final return len(stack) == 0 catches this.
Pushing the closing bracket instead of checking it: only push opening brackets. Close brackets should trigger a match check, not a push.
Wrong map direction: the map should go closing → opening so you can look up what a close bracket expects to find on the stack.

Valid Parentheses — Solution