Maintain String Counts With Minimum and Maximum Queries

# Maintain String Counts With Minimum and Maximum Queries Implement the following stateful `AllOne` class: - `AllOne()` creates an empty structure. - `void inc(string key)` adds one to the key's count, inserting it with count one if absent. - `void dec(string key)` subtracts one from an existing key's count. Remove the key when its count becomes zero. Each decrement is guaranteed to name a present key. - `string getMaxKey()` returns any present key with the largest count, or `""` when empty. - `string getMinKey()` returns any present key with the smallest count, or `""` when empty. Every operation must take `O(1)` average time. Tied keys are equally valid answers; no lexical or insertion-order tie-break is required. ### Example 1 ```text Operations: [AllOne,inc,inc,getMinKey,getMaxKey,inc,getMaxKey,getMinKey] Arguments: [[],["red"],["blue"],[],[],["red"],[],[]] One valid output: [null,null,null,"blue","red",null,"red","blue"] ``` Before the second `inc("red")`, both keys have count one, so either may answer either query. Afterward `red` has count two and `blue` has count one. ### Example 2 ```text Operations: [AllOne,inc,dec,getMinKey,getMaxKey,inc,getMaxKey] Arguments: [[],["cat"],["cat"],[],[],["dog"],[]] Output: [null,null,null,"","",null,"dog"] ``` ### Constraints - `1 <= key.length <= 10`. - Keys consist of lowercase English letters. - Every `dec` call names a key currently in the structure. - At most `50000` calls are made to `inc`, `dec`, `getMaxKey`, and `getMinKey`. ### Clarifications Queries do not change counts. Removing a zero-count key makes it absent, so a later increment starts it again at one. Different instances start independently empty. The `null` entries above denote constructor or void operations, not returned strings. ### What a Strong Answer Covers - Count updates, key creation and removal, and empty queries. - Correct minimum and maximum keys, including legitimate ties. - Ordered operation sequences and independent object lifecycles. - The required average-time bound and storage usage. ### Follow-up Questions - How would the interface change if it needed to return the count as well as the key? - What changes if the caller requires a consistent rule for choosing among tied keys?