All O(1) Data Structure

Design a data structure that supports incrementing/decrementing string counts and retrieving the key with the max or min count, all in O(1) time.

Implement a function that processes an array of operations and an array of arguments:

• "AllOne" — Initializes the data structure.
• "inc" — Increments the count of string key by 1. If key doesn't exist, insert it with count 1.
• "dec" — Decrements the count of string key by 1. If the count reaches 0, remove key.
• "getMaxKey" — Returns one of the keys with the maximum count. If no keys exist, return "".
• "getMinKey" — Returns one of the keys with the minimum count. If no keys exist, return "".

Examples

Example 1:

Input: operations = ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"], args = [[],["hello"],["hello"],[],[],["leet"],[],[]]

Output: [null,null,null,"hello","hello",null,"hello","leet"]

Explanation: inc(hello)→count 1. inc(hello)→count 2. max=min=hello. inc(leet)→count 1. max=hello(2), min=leet(1).

Example 2:

Input: operations = ["AllOne","inc","inc","inc","inc","dec","dec","dec","getMaxKey","getMinKey"], args = [[],["a"],["b"],["b"],["b"],["b"],["b"],["b"],[],[]]

Output: [null,null,null,null,null,null,null,null,"a","a"]

Explanation: After all ops: a=1, b=1 (b incremented to 3 then decremented back to 1). Wait — inc(a)→1, inc(b)→1, inc(b)→2, inc(b)→3, dec(b)→2, dec(b)→1, dec(b)→0 (removed). Max=min=a.

Constraints

• 1 <= key.length <= 10
• key consists of lowercase English letters
• It is guaranteed that dec is never called on a key with count 0
• At most 5 * 10^4 calls to inc, dec, getMaxKey, and getMinKey