Problem Statement

You are asked to design a data structure that supports the following operations in O(1) time complexity:

• inc(key):
  Increments the count of the string key by 1. If the key does not exist, insert it with count = 1.

• dec(key):
  Decrements the count of the string key by 1. If the key’s count becomes 0, remove it from the data structure.

• getMaxKey():
  Returns one of the keys with the maximal count. If no element exists, return an empty string "".

• getMinKey():
  Returns one of the keys with the minimal count. If no element exists, return an empty string "".

Example 1

• Input:

  AllOne allOne = new AllOne();
  allOne.inc("hello");
  allOne.inc("hello");
  allOne.getMaxKey(); // returns "hello"
  allOne.getMinKey(); // returns "hello"

• Explanation:
  "hello" is the only key in the data structure and its count is 2.

Example 2

• Input:

  AllOne allOne = new AllOne();
  allOne.inc("a");
  allOne.inc("b");
  allOne.inc("b");
  allOne.getMaxKey(); // returns "b"
  allOne.getMinKey(); // returns "a"

• Explanation:
  "b" has a count of 2, while "a" has a count of 1.

Example 3

• Input:

  AllOne allOne = new AllOne();
  allOne.inc("a");
  allOne.inc("b");
  allOne.inc("b");
  allOne.dec("b");
  allOne.getMaxKey(); // returns "a" or "b" (both have count 1)
  allOne.getMinKey(); // returns "a" or "b"

• Explanation:
  After decrementing "b", both "a" and "b" have the same count.

Constraints

• All keys are non-empty strings.
• The operations inc, dec, getMaxKey, and getMinKey must all run in O(1) time.
• The data structure should be able to handle a large number of calls efficiently.

2. Hints Before Diving into the Solution

1. Think about supporting O(1) operations:
   Consider using a combination of hash maps to store the key counts and a doubly linked list (DLL) to quickly access the minimum and maximum counts.

2. Bucket-based organization:
   One effective strategy is to group keys by their frequency. Each group (or bucket) represents keys with the same count. This way, you can maintain pointers to the buckets to retrieve the max and min keys in constant time.

Approach 1: Brute Force (Not Optimal)

Description

• Idea:
  Use a hash map (or dictionary) to store the count for each key.
  For inc and dec, update the count in the hash map.
  For getMaxKey and getMinKey, iterate through the entire hash map to find the maximum and minimum counts.

Step-by-Step Walkthrough

1. inc(key):
   • If key is not in the hash map, add it with count 1.
   • Otherwise, increment the count by 1.
2. dec(key):
   • If key is in the hash map, decrement its count.
   • If the count becomes 0, remove the key.
3. getMaxKey():
   • Iterate over all keys to find one with the highest count.
4. getMinKey():
   • Iterate over all keys to find one with the lowest count.

Complexity Analysis

• inc / dec: O(1) per operation (hash map update).
• getMaxKey / getMinKey: O(n) per operation since you need to scan through all keys.

Conclusion

While the brute force approach is simple, it does not meet the O(1) requirement for all operations. This approach is useful for understanding the problem but is not acceptable for an interview solution.