You Can't Take Off a Jacket You Never Wore

Solving balanced parentheses with a dressing room metaphor

Press → or Space to continue

(()()) ())()

(()())

())()

Count Opening & Closing

Opening

Closing

Tracking Pending to Close

Pending to close

Counter Per Type

( )

[ ]

{ }

Action Log

PUT T-Shirt

PUT Sweater

PUT Jacket

TAKE OFF Jacket

TAKE OFF Sweater

TAKE OFF T-Shirt

Action Log

PUT T-Shirt

PUT Sweater

PUT Jacket

TAKE OFF Sweater

Action Log

(

[

{

}

]

[

]

)

Action Log

(

[

]

{

}

)

Stack

empty

Let's see how this works in Python code. We start with an empty stack. This is where we keep the parentheses that are still open. In Python, we implement the stack as a list.

We also define a mapping from each closing symbol to the opening one it matches. That mapping tells us exactly what we expect to find on the stack when a closing appears.

We then go through the input line, one character at a time.

If the character is an opening, we push it onto the stack. Otherwise, we treat it as a closing one. We assume the input contains no letters, numbers, or other symbols.

At that point, we ask: do we have something to close? If the stack is empty, we stop immediately.

If there is something to close, we take the most recent opening. We use pop to get and remove the last item from the stack.

We then use the mapping to check if the opening we pop matches the closing we just encountered. If it doesn't match, the sequence is invalid.

We repeat this until we reach the end of the line. At the very end, only one thing matters: did we close everything we opened?

The time complexity is linear because we process each character exactly once. The space complexity is also linear in the worst case, as we may need to store every opening if none are closed. That gives us an efficient solution.

Counter vs Stack

Single type

Just count!

( ( ) ( ) )

Multiple types

Need a stack!

( [ { } ] )