Solution: All O`one Data Structure

Explore how to create the AllOne data structure by combining a doubly linked list and hash maps to track string key frequencies efficiently. Understand how to perform increment, decrement, getMaxKey, and getMinKey operations all in average constant time, enabling effective frequency management with custom data structures.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

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)$ ...