LFU Cache Python Solution with Tests

lcpy gen -n 460   # by problem number
lcpy gen -s lfu_cache   # by problem name

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation
lfu = LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1, cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is LFU (cnt=1 smallest), invalidate 2. cache=[3,1]
lfu.get(2);      // return -1
lfu.get(3);      // return 3, cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // tie cnt 1 and 3, 1 is LRU, invalidate 1. cache=[4,3]
lfu.get(1);      // return -1
lfu.get(3);      // return 3, cnt(3)=3, cnt(4)=1
lfu.get(4);      // return 4, cnt(4)=2, cnt(3)=3

from collections import OrderedDict, defaultdict


class LFUCache:
    # Time: O(1) amortized per get/put
    # Space: O(capacity)
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val: dict[int, int] = {}
        self.key_to_freq: dict[int, int] = {}
        self.freq_to_keys: dict[int, OrderedDict[int, None]] = defaultdict(OrderedDict)

    def _touch(self, key: int) -> None:
        """Increment frequency of key and move it to the next frequency bucket."""
        freq = self.key_to_freq[key]
        bucket = self.freq_to_keys[freq]
        bucket.pop(key)
        if not bucket:
            if self.min_freq == freq:
                self.min_freq += 1
            del self.freq_to_keys[freq]
        new_freq = freq + 1
        self.key_to_freq[key] = new_freq
        self.freq_to_keys[new_freq][key] = None

    # Time: O(1)
    # Space: O(1)
    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._touch(key)
        return self.key_to_val[key]

    # Time: O(1)
    # Space: O(1)
    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._touch(key)
            return
        if len(self.key_to_val) >= self.capacity:
            # Evict least frequently used; ties broken by least recently used.
            min_bucket = self.freq_to_keys[self.min_freq]
            evict_key, _ = min_bucket.popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]
            if not min_bucket:
                del self.freq_to_keys[self.min_freq]
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1