Valid parentheses: check that brackets nest properly

Given a string made of the brackets (, ), [, ], { and }, decide whether it is properly nested: every opening bracket is closed by a bracket of the same type, and the most recently opened bracket closes first. The empty string is valid.

Interface

Unless you agree on a different interface with the interviewer, assume:

• is_valid(s: str) -> bool

Example

is_valid("()[]{}")  ->  True
is_valid("{[]}")    ->  True
is_valid("([)]")    ->  False   # ] closes while ( is still the innermost
is_valid("(")       ->  False
is_valid("")        ->  True

Constraints

• 0 <= len(s) <= 10^4; s holds only bracket characters.

Clarifying questions

• Can the string contain other characters, and should they be ignored?
• Is the empty string valid?
• Only these three bracket types?

What a strong answer covers

• A stack of open brackets and a map from each closer to its opener.
• Failing on a closer with an empty stack or the wrong opener, and on a non-empty stack at the end.
• O(n) time, O(n) space; an early exit on odd length.
• Tests: empty, single bracket, interleaved types, only closers.

Follow-ups

• Return the length of the longest valid substring.
• Return the fewest insertions that make the string valid.
• Support other characters, or quotes inside which brackets don't count.