A code editor highlights a line in red when its brackets don't line up. Write is_balanced(s) that returns True if the brackets in s are balanced and False otherwise.
s contains only the six characters ( ) [ ] { }. It is balanced when:
- every opening bracket is closed by a bracket of the same kind;
- brackets close in the right order: whatever was opened last must be closed first;
- no closing bracket appears without a matching opener before it.
The empty string is balanced.
is_balanced("([]{})") # True
is_balanced("{[()()]}") # True
is_balanced("([)]") # False (the "[" is closed by ")")
is_balanced("((") # False (never closed)
is_balanced("])") # False (nothing to close)
is_balanced("") # True
Constraints: 0 <= len(s) <= 2 * 10^5.
Repeatedly deleting (), [] and {} pairs until nothing changes works, but it is O(n²) on deeply nested input. Aim for O(n) with a single pass.
Show hint
when you meet a closing bracket, the only opener it may match is the most recent one that is still unmatched. What structure hands you "the most recent unmatched thing" in O(1)?