Facebook Hackercup 2013: Balanced Smileys

Question

On Facebook HackerCup 2013, they asked the following question:

Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(

Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:

• An empty string ""
• One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)
• An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.
• A message with balanced parentheses followed by another message with balanced parentheses.
• A smiley face ":)" or a frowny face ":("

Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.

Balancing parentheses is talked about in a lot of places. E.g. (()) vs ()(). You can count

• '(' = +1
• ')' = -1

Then you have to make sure your sum never falls below 0.

In this question they consider :) and :( as balanced and I wonder how much it changes things. One solution says that you can replace r'[^a-z:() ], '', ':)' -> '}' and ':(' -> '{'.

While I agree with the first sub, why are the last two substitutions valid?

Answer 1

The solution is correct because the "}" and "{" symbols are considered "optional" parentheses.

(:):):(:::) → (}}{}

The left one is an example of an input string, the right is the preprocessed version of it. If you read the algorithm, you see that they keep two values,

min_level, max_level = (0, 0).

Reading the actual solution should convince you.