Valid Parentheses

Problem Description

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

An input string is valid if:

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

Examples

Constraints

• 1 ≤ s.length ≤ 10⁴
• s consists of parentheses only: '()[]{}'.

A Closing Bracket Must Match the Most Recently Opened One

The constraint is about nesting order, not just counts. "([)]" has equal counts of every bracket type but is invalid because ) comes before ] is closed. What you need is the ability to remember the most recent unclosed bracket and compare it against the current closing bracket. A stack handles exactly that.

Push every opening bracket. When you see a closing bracket, the top of the stack must be its match. If it isn’t, or if the stack is empty, the string is invalid. At the end, the string is valid only if the stack is empty (every opener was closed).

Solution 1: Counter Approach (Single Bracket Type Only, to Show Its Failure)

If the string only had one bracket type, you could track a running count of unmatched openers. This fails for multiple types because it can’t distinguish (] from ().

// This only works for a single bracket type: shows why a full stack is needed
class Solution {
    public boolean isValidSingleType(String s) {
        int open = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (c == ')') {
                if (open == 0) return false;
                open--;
            }
        }
        return open == 0;
    }
}

# This only works for a single bracket type: shows why a full stack is needed
class Solution:
    def isValidSingleType(self, s: str) -> bool:
        open_count = 0
        for c in s:
            if c == '(':
                open_count += 1
            elif c == ')':
                if open_count == 0:
                    return False
                open_count -= 1
        return open_count == 0

// This only works for a single bracket type: shows why a full stack is needed
class Solution {
public:
    bool isValidSingleType(std::string s) {
        int open = 0;
        for (char c : s) {
            if (c == '(') open++;
            else if (c == ')') { if (!open) return false; open--; }
        }
        return open == 0;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Single pass.
• Space Complexity: O(1). One counter.

Where it breaks: "(]" returns true with this approach since the count hits 0 correctly. The approach completely fails for multiple bracket types.

Solution 2: Stack

For each character: if it’s an opener, push it. If it’s a closer, check that the stack top is the matching opener. Any mismatch or empty stack on a close character returns false immediately.

import java.util.Stack;
import java.util.Map;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> matching = Map.of(')', '(', '}', '{', ']', '[');

        for (char c : s.toCharArray()) {
            if (matching.containsKey(c)) {
                // closing bracket: stack must have the matching opener on top
                if (stack.isEmpty() || stack.peek() != matching.get(c)) return false;
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        matching = {')': '(', '}': '{', ']': '['}

        for c in s:
            if c in matching:
                # closing bracket: stack must have the matching opener on top
                if not stack or stack[-1] != matching[c]:
                    return False
                stack.pop()
            else:
                stack.append(c)

        return len(stack) == 0

#include <string>
#include <stack>
#include <unordered_map>

class Solution {
public:
    bool isValid(std::string s) {
        std::stack<char> stack;
        std::unordered_map<char, char> matching = {{')', '('}, {'}', '{'}, {']', '['}};

        for (char c : s) {
            if (matching.count(c)) {
                // closing bracket: stack must have the matching opener on top
                if (stack.empty() || stack.top() != matching[c]) return false;
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.empty();
    }
};

Complexity Analysis:

• Time Complexity: O(n). Each character is pushed and popped at most once.
• Space Complexity: O(n). In the worst case (all opening brackets), the stack holds all n characters.

Where it breaks: a string like "(((" has no closing brackets, so stack.isEmpty() returns false at the end. You must always check the stack is empty after the loop, not just that no mismatch was found during it.

Common Mistakes

• Checking stack.size() > 0 instead of stack.isEmpty() at the end. If you forget this final check, "(((" returns true since no mismatch is found during traversal.
• Handling the empty stack case only partially. When a closing bracket arrives and the stack is empty, you must return false immediately. Popping an empty stack crashes the program.
• Using a counter approach for all three bracket types. Maintaining three counters still can’t catch "[(])" style interleaving. A stack is the right tool here, not counters.

Frequently Asked Questions

Can you solve this in O(1) space? No. The stack can grow to O(n) in the worst case (e.g., "(((((("). Any correct solution must be able to remember all unmatched openers, which requires O(n) space.

What if the input contains characters other than brackets? The constraint says s only contains '()[]{}', so you don’t need to handle other characters. In a generalized version, you’d just ignore non-bracket characters.

What does this problem test beyond the algorithm? Interviewers look for clean handling of the empty stack edge case and the final stack.isEmpty() check. Missing either one indicates you’re not thinking through termination conditions.

← All Problems