All O`one Data Structure

Design a container that tracks string keys along with an integer count for each key, supporting all of the following operations in O(1) time (constant time, independent of how many keys or how large the counts are):

• inc(key): If key does not exist in the structure, insert it with a count of 1. Otherwise, increment its existing count by 1.
• dec(key): Decrement the count of key by 1. If the count drops to 0, remove key from the structure entirely. You may assume dec is never called on a key that isn't currently present.
• getMaxKey(): Return any one key that currently has the highest count among all stored keys. If the structure is empty, return the empty string "".
• getMinKey(): Return any one key that currently has the lowest count among all stored keys. If the structure is empty, return the empty string "".

Every operation — inc, dec, getMaxKey, and getMinKey — must run in O(1) time, so scanning through all keys to find a max or min is not acceptable. When multiple keys share the maximum (or minimum) count, any one of them is an acceptable answer.

Examples

Example 1:

Input:

["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["apple"], ["banana"], [], [], ["apple"], [], []]

Output:

[null, null, null, "apple", "apple", null, "apple", "banana"]

Explanation:

• After inc("apple") and inc("banana"), both keys have count 1, so either could validly be returned by getMaxKey or getMinKey; here "apple" happens to be returned for both.
• After inc("apple") again, "apple" has count 2 and "banana" has count 1, so getMaxKey must return "apple" and getMinKey must return "banana".

Example 2:

Input:

["AllOne", "inc", "inc", "dec", "getMaxKey", "getMinKey"]
[[], ["cat"], ["cat"], ["cat"], [], []]

Output:

[null, null, null, null, "cat", "cat"]

Explanation:

"cat" is incremented to a count of 2, then decremented back down to 1. It remains the only key in the structure, so it is returned as both the max and the min.

Constraints

• 1 <= key.length <= 10
• key consists only of lowercase English letters.
• dec is called only on a key that is currently present in the structure with a count of at least 1.
• At most 5 * 10^4 total calls will be made to inc, dec, getMaxKey, and getMinKey combined.