Check That a String of Three Bracket Types Is Properly Nested

Given a string made only of the six bracket characters (, ), [, ], { and }, decide whether its brackets are properly nested.

Function Signature

def is_properly_nested(s: str) -> bool:

Rules

• ( pairs only with ), [ only with ], and { only with }.
• Every closing bracket must close the most recently opened bracket that is still open, and that bracket must be of the same type.
• A closing bracket that appears while no bracket is open makes the string invalid.
• Every opening bracket must eventually be closed; a bracket still open at the end makes the string invalid.
• Pairs may sit side by side (()[]) or inside one another ({[()]}), but they may not cross: in ([)] the ) arrives while [ is the most recently opened bracket, so the string is invalid.
• Return True when the string is properly nested and False otherwise.

Constraints

• 1 <= len(s) <= 10^4
• Every character of s is one of (, ), [, ], {, }.

Examples

Example 1

Input:  s = "{[()]}()"
Output: True

The first six characters nest three pairs inside one another, and the final () sits beside them.

Example 2

Input:  s = "([)]"
Output: False

The ) at index 2 must close the most recently opened bracket, which is [, so the types do not match.

Example 3

Input:  s = "[]{"
Output: False

The { at the end is never closed.

Check Whether Mixed Brackets Are Properly Nested

Hints

1. When a closing bracket arrives, the rules allow exactly one earlier bracket to be its partner: the most recently opened one that is still open.
2. As you read left to right, decide what you must remember about brackets that are still open, and in which order you will need to get them back.
3. Besides a type mismatch, a string fails in two more ways: a closer arrives when nothing is open, or something is still open when the string ends.

Approach

Scan the string left to right and keep a stack of the opening brackets that are still open, most recent on top. An opening bracket is pushed. A closing bracket must match the bracket on top of the stack: if the stack is empty (a closer with nothing open) or the top is a different type (a wrong-type or crossing closer), the answer is False immediately; otherwise the top is popped because that pair is now closed. After the scan the string is valid exactly when the stack is empty, since anything left on it was opened and never closed.

Invariant: after processing a prefix without failing, the stack holds exactly the still-open brackets of that prefix in the order they were opened, so its top is the most recently opened bracket that is still open, which is the only bracket the rules allow the next closer to close. Every rule in the statement maps to one check: same-type pairing and no crossing (top must match), no closer while nothing is open (empty-stack check), and nothing left open (final emptiness check). Pairs side by side and pairs nested inside one another are both accepted because each closer only ever looks at the current top.

Edge cases: a single character is always invalid (a lone opener stays open, a lone closer has nothing to close); an odd-length string always leaves something unmatched; counting brackets per type is not enough, because ([)] and {(}) have balanced counts but cross.

• Time complexity: O(n)
• Space complexity: O(n)