Skip to main content
CodePeetCodePeet
CodePeet 150

Valid Parentheses

EASYProblemSolveExternal Links

Description

You are given a string that contains only bracket characters: round brackets '(' and ')', curly brackets '{' and '}', and square brackets '[' and ']'. Your task is to determine whether the string of brackets is valid.

A string of brackets is considered valid if it satisfies all three of the following rules:

  1. Same type matching: Every opening bracket must be closed by a closing bracket of the same type. For example, '(' must be closed by ')', not by ']' or '}'.

  2. Correct nesting order: Brackets must be closed in the correct order. If you open bracket A and then bracket B, you must close B before you can close A. For instance, '([)]' is invalid because the closing ')' appears before the closing ']', even though '[' was opened after '('.

  3. Complete pairing: Every closing bracket must have a corresponding opening bracket before it, and every opening bracket must eventually be closed.

Your function should return true if the string is valid, and false otherwise.

Examples

Example 1

Input: s = "()"

Output: true

Explanation: There is exactly one opening bracket '(' followed by its matching closing bracket ')'. The pair is correctly matched, and no brackets are left unmatched.

Example 2

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

Output: true

Explanation: The string contains three separate pairs placed sequentially: '()' matches, '[]' matches, and '{}' matches. Each pair is independently valid, and all brackets are accounted for.

Example 3

Input: s = "(]"

Output: false

Explanation: The opening bracket '(' requires a closing ')' to match, but instead it encounters ']'. Since the bracket types do not match, the string is invalid.

Example 4

Input: s = "([])"

Output: true

Explanation: The outermost pair is '(' and ')'. Inside it, '[]' forms a valid nested pair. The inner pair is properly closed before the outer pair, satisfying the correct nesting order rule.

Example 5

Input: s = "([)]"

Output: false

Explanation: Reading left to right: '(' is opened, then '[' is opened. The next character ')' tries to close '(', but '[' was opened more recently and hasn't been closed yet. The nesting order is violated — the most recently opened bracket must be closed first.

Constraints

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

Editorial

Brute Force

Intuition

The most intuitive way to check if brackets are valid is to repeatedly find and remove matching adjacent pairs. Think of it like a game: scan the string for any directly adjacent matching pair like '()', '[]', or '{}'. When you find one, remove it from the string. Then scan again. Keep repeating until either the string becomes empty (valid) or no more pairs can be found (invalid).

Imagine you have a string of colored beads, where matching pairs of beads cancel each other out when touching. You keep removing touching pairs until either all beads are gone or you are left with beads that cannot be paired.

For example, with '({[]})': remove '[]' → '({})' → remove '{}' → '()' → remove '()' → '' (empty, so valid).

This works because valid bracket strings have the property that there is always at least one adjacent matching pair somewhere inside them. Removing such a pair preserves the validity of the remaining string.

Step-by-Step Explanation

Let's trace through with s = "{[()]}":

Step 1: Scan for adjacent matching pairs in "{[()]}".

  • Index 0-1: '{' and '[' → not a match
  • Index 1-2: '[' and '(' → not a match
  • Index 2-3: '(' and ')' → MATCH! Remove this pair.

Step 2: After removing '()': string becomes "{[]}".

  • Index 0-1: '{' and '[' → not a match
  • Index 1-2: '[' and ']' → MATCH! Remove this pair.

Step 3: After removing '[]': string becomes "{}".

  • Index 0-1: '{' and '}' → MATCH! Remove this pair.

Step 4: After removing '{}': string becomes "" (empty).

Step 5: String is empty → return true. All brackets were validly paired.

Now let's try an invalid example, s = "([)]":

Step 1: Scan for adjacent matching pairs in "([)]".

  • Index 0-1: '(' and '[' → not a match
  • Index 1-2: '[' and ')' → not a match
  • Index 2-3: ')' and ']' → not a match
  • No adjacent pairs found!

Step 2: String is not empty but no pairs can be removed → return false.

Algorithm

  1. Repeat the following until no changes are made in a full pass:
    • Scan the string for adjacent matching pairs: '()', '[]', '{}'
    • If a pair is found, remove it from the string
  2. After no more removals are possible, check if the string is empty
  3. If empty, return true (all brackets matched). Otherwise, return false.

Code

class Solution {
public:
    bool isValid(string s) {
        // Repeatedly remove adjacent matching pairs
        string prev;
        do {
            prev = s;
            size_t pos;
            // Remove all occurrences of "()", "[]", "{}"
            while ((pos = s.find("()")) != string::npos)
                s.erase(pos, 2);
            while ((pos = s.find("[]")) != string::npos)
                s.erase(pos, 2);
            while ((pos = s.find("{}")) != string::npos)
                s.erase(pos, 2);
        } while (s != prev);
        
        return s.empty();
    }
};
class Solution:
    def isValid(self, s: str) -> bool:
        # Repeatedly remove adjacent matching pairs
        while '()' in s or '[]' in s or '{}' in s:
            s = s.replace('()', '')
            s = s.replace('[]', '')
            s = s.replace('{}', '')
        
        return s == ''
class Solution {
    public boolean isValid(String s) {
        // Repeatedly remove adjacent matching pairs
        String prev;
        do {
            prev = s;
            s = s.replace("()", "");
            s = s.replace("[]", "");
            s = s.replace("{}", "");
        } while (!s.equals(prev));
        
        return s.isEmpty();
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case (like deeply nested brackets "(((...)))" ), each pass through the string removes only one pair (2 characters). With n characters total, we might need n/2 passes. Each pass scans the string which takes O(n) time. Total: O(n/2 × n) = O(n²).

Space Complexity: O(n)

String replacement creates new string objects. In the worst case, we have intermediate strings of various lengths, but the maximum space used at any point is proportional to the original string length.

Why This Approach Is Not Efficient

The brute force approach of repeatedly scanning and removing pairs has O(n²) time complexity. With n up to 10^4, this means up to 10^8 operations in the worst case — dangerously close to time limits.

The core inefficiency is that we rescan the entire string after each removal. When we remove a pair, we lose track of our position and start over from the beginning.

The key insight for improvement is about the nesting structure of valid brackets: the most recently opened bracket must be the first one to close. This is exactly the Last-In-First-Out (LIFO) principle — the defining characteristic of a stack data structure. Instead of repeatedly rescanning, we can process each character exactly once by using a stack to remember which brackets are still open.

Optimal Approach - Stack

Intuition

Think about reading brackets left to right, just as you would read a sentence. When you encounter an opening bracket, you need to remember it because its matching closer will come later. But here is the crucial pattern: if you open bracket A, then open bracket B inside it, bracket B must close before bracket A can close. The last bracket opened is always the first one that needs closing.

This "last in, first out" behavior is exactly what a stack provides. As we read through the string:

  • When we see an opening bracket ('(', '[', or '{'), we push it onto the stack. This is like saying "I need to match this later."
  • When we see a closing bracket (')', ']', or '}'), we check the top of the stack. The top holds the most recently unmatched opening bracket. If it matches the current closing bracket, we pop it off (the pair is resolved). If it does not match, or if the stack is empty (no opener to match with), the string is invalid.

After processing every character, the stack should be empty. If any opening brackets remain on the stack, they were never closed, making the string invalid.

This approach processes each character exactly once, giving us an efficient O(n) solution.

Step-by-Step Explanation

Let's trace through with s = "{[()]}":

Step 1: Initialize an empty stack. Process character '{' (index 0).

  • '{' is an opening bracket → push onto stack.
  • Stack: ['{']

Step 2: Process character '[' (index 1).

  • '[' is an opening bracket → push onto stack.
  • Stack: ['{', '[']

Step 3: Process character '(' (index 2).

  • '(' is an opening bracket → push onto stack.
  • Stack: ['{', '[', '(']

Step 4: Process character ')' (index 3).

  • ')' is a closing bracket. Check top of stack: '('.
  • Does '(' match ')'? YES → Pop '(' from stack.
  • Stack: ['{', '[']

Step 5: Process character ']' (index 4).

  • ']' is a closing bracket. Check top of stack: '['.
  • Does '[' match ']'? YES → Pop '[' from stack.
  • Stack: ['{']

Step 6: Process character '}' (index 5).

  • '}' is a closing bracket. Check top of stack: '{'.
  • Does '{' match '}'? YES → Pop '{' from stack.
  • Stack: []

Step 7: All characters processed. Is the stack empty? YES → return true.

The string "{[()]}" is valid because every opening bracket found its matching closer in the correct order.

Stack-Based Bracket Validation: {[()]} — Opening brackets are pushed onto the stack. When a closing bracket appears, we pop the top and check if the pair matches. An empty stack at the end means the string is valid.

Algorithm

  1. Create an empty stack and a mapping of matching bracket pairs
  2. For each character in the string:
    • If it is an opening bracket ('(', '[', or '{'), push it onto the stack
    • If it is a closing bracket:
      • If the stack is empty, return false (no opener to match)
      • Pop the top element from the stack
      • If the popped opener does not match the current closer, return false
  3. After processing all characters, check if the stack is empty
  4. Return true if empty (all brackets matched), false otherwise

Code

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char, char> matching = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                // Closing bracket
                if (st.empty() || st.top() != matching[c]) {
                    return false;
                }
                st.pop();
            }
        }
        
        return st.empty();
    }
};
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        matching = {')': '(', ']': '[', '}': '{'}
        
        for char in s:
            if char in '([{':
                stack.append(char)
            else:
                # Closing bracket
                if not stack or stack.pop() != matching[char]:
                    return False
        
        return len(stack) == 0
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> matching = Map.of(
            ')', '(',
            ']', '[',
            '}', '{'
        );
        
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                // Closing bracket
                if (stack.isEmpty() || !stack.pop().equals(matching.get(c))) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string exactly once, processing each of the n characters in constant time. Each character triggers either a push (O(1)) or a pop + comparison (O(1)). The hash map lookup for matching pairs is also O(1). Total: n × O(1) = O(n).

Space Complexity: O(n)

In the worst case, all characters are opening brackets (e.g., "((((" with length n), and we push all of them onto the stack. The stack would hold n elements. The matching map uses constant space O(1) since it always has exactly 3 entries.