Katkat
Back

Check That a String of Three Bracket Types Is Properly Nested

OracleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Decide whether a string made of round, square and curly brackets is properly nested, meaning every closing bracket matches the most recently opened bracket of the same type and nothing is left open. Tests careful handling of nesting order, crossing pairs and unmatched brackets at either end.

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.