Solution: All O`one Data Structure

Explore how to design and implement the AllOne data structure using a custom doubly linked list and hash maps to enable constant-time updates and queries of string key frequencies. Understand the methods inc, dec, getMaxKey, and getMinKey to efficiently manage frequency-based operations and maintain optimal performance.

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