Problem statement

Given a string s containing just '(', ')', '{', '}', '[' and ']', determine whether it is valid:

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

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

Constraints

• 0 <= s.length <= 40
• s consists only of the six bracket characters.

Hints for Valid Parentheses

1. Hint 1

   Push every opener on a stack; a closer must match the top of the stack.

2. Hint 2

   Valid iff no mismatch occurs and the stack ends empty.

How to solve Valid Parentheses

Brackets nest, so at any point the only opener a closing bracket is allowed to match is the most recent one still open. That is last-in-first-out — precisely a stack. Counting brackets is not enough: "([)]" has the right counts and is still invalid, because the order is wrong.

Approach

1. Keep a map from each closing bracket to the opening bracket it expects.
2. Scan the string once. On an opener, push it.
3. On a closer, pop the top and check it is the matching opener. If the stack is empty or the popped bracket is the wrong type, the string is invalid — return immediately.
4. After the scan, the string is valid only if the stack is empty. Anything left over is an opener that was never closed.

Why it works

The stack always holds the openers that are still waiting to be closed, innermost on top. When a closer arrives, correct nesting demands it pair with that innermost opener — no other pairing can produce a valid string. So the greedy match at the top is forced, never a guess, and one pass settles it.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• A closer arriving on an empty stack is invalid, not something to skip. (The Python solution tests not st explicitly; the JavaScript one gets it free, since pop() on an empty array returns undefined, which never equals a bracket.)
• Finishing the scan without a mismatch is not enough — unclosed openers left on the stack mean invalid.
• The empty string is valid: the loop never runs and the stack ends empty.

Reference solution

Python

def isValid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    st = []
    for ch in s:
        if ch in "([{":
            st.append(ch)
        else:
            if not st or st.pop() != pairs[ch]:
                return False
    return not st

Java

public static boolean isValid(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char ch : s.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);
        } else {
            if (st.isEmpty()) return false;
            char top = st.pop();
            if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) return false;
        }
    }
    return st.isEmpty();
}

C++

bool isValid(string s) {
    vector<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push_back(ch);
        } else {
            if (st.empty()) return false;
            char top = st.back();
            st.pop_back();
            if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) return false;
        }
    }
    return st.empty();
}

JavaScript

var isValid = function(s) {
    const pairs = { ")": "(", "]": "[", "}": "{" };
    const st = [];
    for (const ch of s) {
        if (ch === "(" || ch === "[" || ch === "{") {
            st.push(ch);
        } else {
            if (st.pop() !== pairs[ch]) return false;
        }
    }
    return st.length === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy