Valid parentheses: counting brackets passes the examples, fails hidden tests

Question

My idea was that every opening bracket needs a matching closing one, so I count them:

def is_valid(s):
    return (s.count("(") == s.count(")")
        and s.count("[") == s.count("]")
        and s.count("{") == s.count("}"))

All the examples pass, but the hidden tests fail. What am I not seeing?

Kenji Morita · Accepted Answer

Counts tell you how many, but not in what order. Two inputs your version accepts:

")(": one of each, but it closes before it opens.
"([)]": every type balances, but the square bracket closes inside the round pair.

Brackets must close in the reverse order they opened, last in first out, and that is exactly what a stack does:

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

Both checks matter: not stack before popping catches a closer with nothing open, and return not stack at the end catches openers that never got closed, like "((".

Fatima Zahra Benali · Answer

"([)]" is a great counterexample. Passed everything with the stack. I am adding "think of an input where the order is wrong" to my checklist.