351. All O`one Data Structure
Design a counter that tracks string keys and answers extreme queries in constant time. Implement a class AllOne supporting four operations:
inc(key)— insertkeywith count 1 if it is absent, otherwise raise its count by 1.dec(key)— lowerkey's count by 1; when the count reaches 0, remove the key entirely.decis only ever called on a key that currently exists.getMaxKey()— return a key whose count is the highest, or the empty string if no keys exist. (Python:get_max_key.)getMinKey()— return a key whose count is the lowest, or the empty string if no keys exist. (Python:get_min_key.)
Each operation must run in O(1) average time. To keep answers unambiguous, every judged test guarantees that whenever a max/min query runs, either the structure is empty or exactly one key holds the extreme count.
The grader feeds your class a script of operations from stdin and prints one line per query — the returned key, or none when your method returns the empty string.
Example 1:
Input: inc("hello"), inc("hello"), getMaxKey(), getMinKey(), inc("leet"), getMaxKey(), getMinKey()
Output: "hello", "hello", then "hello", "leet"
Explanation: After two increments, hello (count 2) is both the max and the min. Once leet arrives with count 1, hello stays the max and leet becomes the min.
Example 2:
Input: inc("a"), inc("b"), inc("b"), getMaxKey(), dec("b"), dec("b"), getMaxKey(), getMinKey()
Output: "b", then "a", "a"
Explanation: b climbs to count 2 and wins the max query. Two decrements erase b completely, leaving a (count 1) as both extremes.
Constraints:
- 1 ≤ Q ≤ 5 * 10⁴
- 1 ≤ key.length ≤ 10; keys consist of lowercase English letters
- dec is only ever called on a key that is currently present
- Whenever max or min is queried, either no keys exist or exactly one key holds the extreme count, so the answer is unambiguous
Hints:
A hash map of counts gives O(1) inc and dec, but answering max/min means scanning every key. What would you need to keep sorted so the extremes are always at the ends — the keys, or the counts?
A count only ever changes by exactly ±1. Keep a doubly linked list of buckets, one bucket per distinct count in ascending order, each holding the set of keys at that count: inc and dec just move a key into a neighboring bucket, creating or deleting buckets as needed.
The extremes then cost nothing: min is any key in the first bucket, max any key in the last. Sentinel head/tail buckets remove every edge case; just remember to unlink a bucket the moment it empties.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: inc("hello") ×2, max, min, inc("leet"), max, min
Expected output: "hello", "hello", "hello", "leet"