Design a String Frequency Tracker (incr/decr/getMax/getMin)

Problem: Design a data structure that supports the following operations as efficiently as possible:

• incr(String s): increment the frequency of string s (inserting it with frequency 1 if not present).
• decr(String s): decrement the frequency of string s; remove it entirely if frequency drops to 0.
• getMax(): return a string with the maximum frequency.
• getMin(): return a string with the minimum frequency.

Example: incr("hello") -> getMax() = "hello" incr("world"); incr("world") -> getMax() = "world" decr("hello") -> getMin() = "world"

Approach: Maintain a hashmap from string -> frequency, plus a doubly linked list of frequency "buckets" (each bucket holding the set of strings with that frequency), similar to the classic LFU-cache technique. incr/decr move a string between adjacent frequency buckets in O(1); getMax/getMin read from the head/tail bucket in O(1).