Sticker Cache With Least-Frequent Eviction

A chat app caches sticker images. Design a class StickerCache that holds at most capacity stickers and, when it must make room, evicts the one used the fewest times:

• StickerCache(capacity): capacity >= 1.
• get(key) returns the stored value, or -1 if key is absent. A successful get is one use of key.
• put(key, value) stores or replaces the value. Replacing an existing key counts as one use. A new key starts with a use count of 1; if the cache is already full, first evict the key with the smallest use count, and among keys tied on that count, the one whose last use is the oldest.

Examples

ops:  ["StickerCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
args: [[2], [1, "a"], [2, "b"], [1], [3, "c"], [2], [3], [4, "d"], [1], [3], [4]]
Output: [None, None, None, "a", None, -1, "c", None, -1, "c", "d"]
Explanation: put(3) evicts key 2 (used once, key 1 was used twice). Before put(4) keys 1 and 3
are both at two uses; key 1's last use is older, so it is evicted.

Constraints

• 1 <= capacity <= 10**4; keys are integers, values strings or integers
• Up to 2 * 10**4 calls in total
• Target: get and put in O(1) average time; scanning all keys to find the victim is too slow

Goals

• Group keys into buckets by use count so the least used key is found in O(1)
• Break ties inside a bucket by recency
• Track the smallest non-empty use count without scanning