The tell: Matching nested pairs, where the most recent opener must close first.
How you get there
1Push every opening bracket.
2On a closer, the top of the stack must be its matching opener.
3At the end the stack must be empty, or some opener was never closed.
Solution
Python
def is_valid(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
Time
O(n)
Space
O(n)
What goes wrong
Returning True without the final emptiness check accepts '((('.