> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# All O`one Data Structure Python Solution

> Tested Python solution for LeetCode 432 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 432, [Hard](/catalog/hard). Topics: [Hash Table](/catalog/topics/hash-table), [Linked List](/catalog/topics/linked-list), [Design](/catalog/topics/design), Doubly-Linked List. [View on LeetCode](https://leetcode.com/problems/all-oone-data-structure/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 432   # by problem number
lcpy gen -s all_oone_data_structure   # by problem name
```

## Problem

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the `AllOne` class:

* `AllOne()` Initializes the object of the data structure.
* `inc(String key)` Increments the count of the string `key` by `1`. If `key` does not exist in the data structure, insert it with count `1`.
* `dec(String key)` Decrements the count of the string `key` by `1`. If the count of `key` is `0` after the decrement, remove it from the data structure. It is guaranteed that `key` exists in the data structure before the decrement.
* `getMaxKey()` Returns one of the keys with the maximal count. If no element exists, return an empty string `""`.
* `getMinKey()` Returns one of the keys with the minimum count. If no element exists, return an empty string `""`.

Note that each function must run in `O(1)` average time complexity.

### Examples

```
Input
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
Output
[null, null, null, "hello", "hello", null, "hello", "leet"]

Explanation
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"
```

### Constraints

* `1 <= key.length <= 10`
* `key` consists of lowercase English letters.
* It is guaranteed that for each call to `dec`, `key` exists in the data structure.
* At most `5 * 10^4` calls will be made to `inc`, `dec`, `getMaxKey`, and `getMinKey`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/all_oone_data_structure/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/all_oone_data_structure/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations


class Bucket:
    def __init__(self, count: int) -> None:
        self.count = count
        self.keys: set[str] = set()
        self.prev: Bucket = self
        self.next: Bucket = self

    def insert_after(self, node: Bucket) -> None:
        node.prev = self
        node.next = self.next
        self.next.prev = node
        self.next = node

    def unlink(self) -> None:
        self.prev.next = self.next
        self.next.prev = self.prev
        self.prev = self.next = self


class AllOne:
    # Doubly linked list of buckets ordered by count, each holding the keys with that
    # count. inc/dec move a key at most one bucket away, so no search is ever needed.
    # Time: O(1) per operation
    # Space: O(n) over the distinct keys stored
    def __init__(self) -> None:
        self.sentinel = Bucket(0)
        self.key_bucket: dict[str, Bucket] = {}

    # Time: O(1)
    # Space: O(1)
    def inc(self, key: str) -> None:
        bucket = self.key_bucket.get(key)
        if bucket is None:
            # New key: it lands at count 1, the bucket closest to the head.
            target = self.sentinel.next
            if target.count != 1:
                target = Bucket(1)
                self.sentinel.insert_after(target)
        else:
            target = bucket.next
            if target.count != bucket.count + 1:
                target = Bucket(bucket.count + 1)
                bucket.insert_after(target)
        self._move(key, bucket, target)

    # Time: O(1)
    # Space: O(1)
    def dec(self, key: str) -> None:
        bucket = self.key_bucket.pop(key)
        target = bucket.prev
        if bucket.count > 1:
            if target.count != bucket.count - 1:
                target = Bucket(bucket.count - 1)
                bucket.prev.insert_after(target)
            self._move(key, bucket, target)
        bucket.keys.discard(key)
        if not bucket.keys:
            bucket.unlink()

    # Time: O(1)
    # Space: O(1)
    def get_max_key(self) -> str:
        return next(iter(self.sentinel.prev.keys), "")

    # Time: O(1)
    # Space: O(1)
    def get_min_key(self) -> str:
        return next(iter(self.sentinel.next.keys), "")

    # Time: O(1)
    # Space: O(1)
    def _move(self, key: str, source: Bucket | None, target: Bucket) -> None:
        if source is not None:
            source.keys.discard(key)
        target.keys.add(key)
        self.key_bucket[key] = target
        if source is not None and not source.keys:
            source.unlink()
```

## Complexity

| Time | Space |
| - | - |
| O(1) per operation | O(n) over the distinct keys stored |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.