We’re preparing your current view and syncing the latest data.
Design a data structure to store strings with the ability to increment, decrement the count of keys, and return a key with the maximum count and a key with the minimum count. The data structure should support the following operations: All O(1) time complexity. 1. Inc(key): Increments the count of the string key by 1. If the key does not exist, insert it with count 1. 2. Dec(key): Decrements the count of the string key by 1. If the key's count becomes 0, remove it from the data structure. If the key does not exist, do nothing. 3. GetMaxKey(): Return one of the keys with the maximal count. If no key exists, return an empty string. 4. GetMinKey(): Return one of the keys with the minimum count. If no key exists, return an empty string.
The input will be a sequence of function calls (Inc, Dec, GetMaxKey, GetMinKey) with respective string arguments where applicable.
For GetMaxKey and GetMinKey calls, output the corresponding key as a string. For Inc and Dec there is no output.
All operations must be done in O(1) time. Keys consist of lowercase English letters only.
Example 1
Input
Inc("hello"), Inc("hello"), GetMaxKey(), GetMinKey(), Inc("leet"), GetMaxKey(), Dec("hello"), GetMaxKey(), GetMinKey()Output
"hello", "hello", "hello", "hello", "leet"
Explanation
Initially, inc "hello" twice, so count of hello = 2. Both max and min keys are "hello". Then inc "leet" once, now hello=2, leet=1. Max key is "hello". Dec "hello" once, now hello=1. Max key and min key can be either "hello" or "leet". Here, output is shown for one possibility.