All-in-One Counter

Build a KeyCounter class that counts string keys and can name a key with the highest or the lowest count at any moment, with every call taking about the same time however many keys there are.

• KeyCounter() starts with no keys.
• inc(key) adds 1 to the key's count. A new key starts at 0, so its count becomes 1.
• dec(key) takes 1 from the key's count. A key whose count reaches 0 is removed, and decreasing a key that is not there does nothing.
• count(key) returns the key's count, or 0 if it is not there.
• max_key() returns a key with the highest count, and min_key() a key with the lowest count. If several keys tie, return any one of them. With no keys, both return the empty string ''.

Examples

kc = KeyCounter()
kc.inc('apple')
kc.inc('apple')
kc.inc('pear')
kc.max_key()        # returns 'apple'
kc.min_key()        # returns 'pear'
kc.dec('apple')
kc.dec('apple')
kc.count('apple')   # returns 0
kc.max_key()        # returns 'pear'

Constraints

• Up to 250,000 calls; keys are non-empty strings
• With tens of thousands of keys and tens of thousands of questions, looking through all the keys for max_key or min_key is far too slow.