Solution: All O`one Data Structure

Explore the design of the AllOne data structure that tracks string key frequencies and supports efficient increment, decrement, getMaxKey, and getMinKey operations. Understand how combining doubly linked lists with hash maps allows all operations to run in constant time, optimizing both time and space complexity.

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