Facebook Hackercup 2013: Balanced Smileys 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?
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.