20. Valid Parentheses

Problem Statement

You are given a string s that contains only the characters '(', ')', '{', '}', '[', and ']', Your task is to determine whether the string is valid.

A string is considered valid if all of the following hold:

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

Return True if s is valid; otherwise, return False.

Constraints:

• $1 \leq$ s.length $\leq 10^{4}$
• s consists of parentheses only ‘()[]{}‘.

Examples

The examples below illustrate a few typical outcomes:

Optimal Solution: Stack-based Validation

The optimal approach is to maintain a stack of the closing brackets we expect to see next, which lets us verify correctness as we scan the string once. Whenever we encounter an opening bracket, we push its matching closing bracket onto the stack, recording what must appear later. When we encounter a closing bracket, it must match the stack’s top; otherwise, the order or type is incorrect, and the string is invalid. A closing bracket with an empty stack is also immediately invalid because there is nothing to match. After processing all characters, the stack must be empty; any remaining expected closers indicate that there are unmatched openings. This avoids any repeated scanning because every character is processed once.

This algorithm is implemented as follows:

1. Initialize an empty stack expected.
2. Scan characters of s from left to right.
3. If the character is an opening bracket, push its matching closing bracket onto expected.
4. Otherwise (it is a closing bracket):
   1. If the stack is empty, return False (nothing to match).
   2. Pop the top element and compare it to the current character; if they differ, return False.
5. After the scan ends, return True only if the stack is empty (no unmatched openers remain).

Here is a visual representation of the algorithm discussed above:

1 / 6

Code Implementation

def isValid(s):
    # Map each opening bracket to the closing bracket it requires
    open_to_close = {
        '(': ')',
        '[': ']',
        '{': '}'
    }

    # Stack of expected closing brackets:
    # the top element is the next closing bracket we must see
    expected = []

    # Process the string from left to right
    for ch in s:
        # If we see an opener, push the closer we will need later
        if ch in open_to_close:
            expected.append(open_to_close[ch])
        else:
            # We saw a closing bracket; it must match the latest expectation
            if not expected:
                # No opening bracket exists for this closer
                return False

            # Pop the expected closer and compare
            needed = expected.pop()
            if ch != needed:
                return False

    # If the stack is empty, every opener found its matching closer
    return len(expected) == 0


# driver code
def main():
    cases = ["({[]})", "{[(])}", "(((())))", "][", "{[()]}[]"]
    
    for i in range(len(cases)):
        s = cases[i]
        print(i + 1, ".\tInput: \"", s, "\"", sep = "")
        print("\tIs valid?    :", "Yes" if isValid(s)  else "No")
        print("-"*75)

if __name__ == "__main__":
    main()

Time Complexity

The time complexity of this solution is $O(n)$ because each character is pushed to or popped from the stack at most once.

Space Complexity

The space complexity of this solution is $(n)$ because, in the worst case, when the string contains only opening brackets, the stack may hold up to $n$ expected closers.

Common Pitfalls

A few small habits prevent most mistakes on this problem:

• Always guard against popping an empty stack: Any closing bracket that appears when the stack is empty must return False immediately.
• Use a meaningful, consistent stack: Either store opening brackets (and check pairs on close) or store expected closing brackets. Mixing the two leads to subtle bugs.
• Early exits are a feature, not an optimization trick: As soon as a mismatch occurs, the final answer cannot recover; returning immediately keeps the logic clean.
• Quick edge checks help with debugging: Strings of odd length can never be valid, and a valid string must end with an empty stack.