Solution: All O`one Data Structure

Explore designing a custom data structure that tracks string frequencies with efficient updates and queries. Understand the use of doubly linked lists combined with hash maps to achieve average constant-time complexity for incrementing, decrementing, and retrieving max or min frequency keys. This lesson helps you apply these principles to implement the AllOne class effectively, deepening your grasp of advanced custom data structure design.

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