#!/usr/bin/python
#-*- coding:utf-8 -*-

"""
When you see 'duplicates' related questions you should immediately
hint yourself with the most powerful set of data structures that solve
this type of problem. Taking Java as an example, typical data structures
are HashMap and HashSet which are normally used to count or mark presense of
uniqueness.

In Python, there are also set() and dict() (i.e., '{}') for you to use.

In C, there are bitmap and lookup table. Highly recommend you to understand
the principles before you jump to a solution.

In this problem, no matter how you reduce the form of the array of characters,
you are always removing characters that appear more than once. Since you did not
mention clearly if the interviewer wants the reduced array or the list of
reduction steps, I assume it's the reduced array.

As you listed in your examples:

Input: [a,a,b,b,b,a,c] Output: [c]
Input: [a,b,c,c,b,a,a] Output: []

On the other hand, you should also ask the interviewer if the original "Array"
is mutable or immutable and if extra memory is allowed to allocate to solve
this problem.

From the hint, it seems a stack solution is possible but not necessary. Stack is used
often if the order of something makes a difference to your output.
Here the order of the removal steps don't really affect the output.
I.e., you can remove all 'a' first or all 'b' first, the output is always
[c] in the first example. You can remove all 'a' first, or all 'c' first, or all 'b' first,
the output in always [] in the second example.

A dict/HashMap solution is way more intutitive.

"""

"""
   This solution gives you worst case
   O(n) time complexity if 'n' is length of the array.
   Worst case is that all characters are unique in array.

   This solution allocates O(n) worst case extra memory due to use of dict.
   Worst case is that all characters are unique in array.

"""
def reduce_duplicates_dict(arr):
   # initialize a dict
   s = {}
   for i in xrange(0, len(arr)):
       if arr[i] not in s:
           s[arr[i]] = 1
       else:
           s[arr[i]] += 1
   result = []

   for key, value in s.iteritems():
       if value < 2:
           result.append(key)
   return result

if __name__ == "__main__":
   # using dict
   print(reduce_duplicates_dict(['a', 'a', 'b', 'b', 'b', 'c']))
   print(reduce_duplicates_dict(['a','b','b','a','a']))