Editor

Where the Brackets Go Wrong

#595 · Stacks and queues · Intermediate · 65 XP · about 12 min

A code editor does more than say "unbalanced": it highlights the bracket that is wrong. Write first_error(text) that returns the position (index) of the first bracket that breaks the balance of the round (), square [] and curly {} brackets in text, or -1 when the brackets are balanced. Every other character is ignored.

Read the text from left to right:

  • A closing bracket is wrong when nothing is open, or when the bracket open most recently is of a different kind. Return its position at once.
  • If the text ends while brackets are still open, return the position of the earliest one that was never closed.

Examples

first_error('(a[b]c)')  # returns -1
first_error('{[}')      # returns 2
first_error('x)')       # returns 1
first_error('((a)')     # returns 0

In '{[}' the } at position 2 arrives while the [ is the most recent open bracket, so it is the wrong one. In '((a)' the bracket at position 1 is closed, and the one at position 0 never is.

Constraints

  • 0 <= len(text) <= 100,000

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.