Practice/LinkedIn/Leetcode 432. All O`one Data Structure

Leetcode 432. All O`one Data Structure

CodingMust

Problem

Design and implement a data structure that tracks the frequency of string keys and supports the following operations efficiently:

• inc(key): Increment the frequency count of the given key by 1. If the key doesn't exist, insert it with a count of 1.
• dec(key): Decrement the frequency count of the given key by 1. If the key's count becomes 0 after decrementing, remove it from the data structure. If the key doesn't exist, do nothing.
• getMaxKey(): Return any key that has the maximum frequency count. If no keys exist, return an empty string.
• getMinKey(): Return any key that has the minimum frequency count. If no keys exist, return an empty string.

Requirements

1. All operations must run in O(1) average time complexity
2. When a key's count reaches zero, it must be removed from the data structure
3. For getMaxKey() and getMinKey(), any key with the respective frequency is acceptable when multiple keys share the same max or min frequency
4. Return an empty string from getMaxKey() or getMinKey() when no keys exist

Constraints

• 1 ≤ Total number of operations ≤ 50,000
• 1 ≤ key.length ≤ 10
• key consists of lowercase English letters only
• It is guaranteed that for each dec operation, the key exists in the data structure if its count is greater than 0

Examples

Example 1:

` Operations: ["inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] Arguments: [["hello"], ["hello"], [], [], ["world"], [], []] Output: [null, null, "hello", "hello", null, "hello", "world"] Explanation:

• inc("hello"): hello has count 1
• inc("hello"): hello has count 2
• getMaxKey(): returns "hello" (count 2)
• getMinKey(): returns "hello" (count 2, only key)
• inc("world"): world has count 1
• getMaxKey(): returns "hello" (count 2)
• getMinKey(): returns "world" (count 1) `

Example 2:

` Operations: ["inc", "inc", "inc", "dec", "dec", "getMaxKey", "getMinKey"] Arguments: [["a"], ["b"], ["a"], ["a"], ["a"], [], []] Output: [null, null, null, null, null, "b", "b"] Explanation:

• inc("a"): a has count 1
• inc("b"): b has count 1
• inc("a"): a has count 2
• dec("a"): a has count 1
• dec("a"): a has count 0, removed
• getMaxKey(): returns "b" (only remaining key)
• getMinKey(): returns "b" (only remaining key) `