Solution: All O`one Data Structure

Statement

Design a data structure that tracks the frequency of string keys and allows for efficient updates and queries.

Implement the AllOne class with these methods:

• Constructor: Initializes the data structure.

• inc(String key): Increases the count of the given key by $1$. If the key is absent, insert it with a count of $1$.

• dec(String key): Decreases the count of the given key by $1$. If the count becomes $0$ after decrementing, remove the key entirely. The assumption is that the key exists when this function is called.

• getMaxKey(): Returns any one key with the highest count. If the data structure is empty, return an empty string.

• getMinKey(): Returns any one key with the lowest count. If the data structure is empty, return an empty string.

Note: All operations must be performed in average $O(1)$ ...