Design a String Frequency Tracker

Problem Design a data structure that tracks the frequency of strings and supports incrementing, decrementing, and reporting a maximum- and a minimum-frequency string, all as efficiently as possible — ideally O(1) per operation.

Input / Output

• Input: a stream of operations — incr(s), decr(s), getMax(), getMin().
• Output:
  • incr(s) — increments s's frequency, inserting it at 1 if absent.
  • decr(s) — decrements s's frequency, removing s entirely if it reaches 0.
  • getMax() — any string with the highest frequency, or "" if the structure is empty.
  • getMin() — any string with the lowest frequency, or "" if empty.

Constraints

• Up to ~10^5 operations, and every one should be O(1) — which rules out a heap (O(log n)) and rescanning the map (O(n)).
• decr on an absent string is a no-op.
• Ties are broken arbitrarily: any string sitting at the extreme frequency is an acceptable answer.

Example

• incr("hello") → getMax() = "hello"
• incr("world"), incr("world") → getMax() = "world", getMin() = "hello"
• decr("hello") → "hello" falls to 0 and is removed, so getMin() = "world" — the case proving empty buckets must be unlinked, or getMin would keep reading a stale frequency.