## Algorithm

Problem Name: 432. All O`one Data Structure

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.

Example 1:

```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` is existing in the data structure.
• At most `5 * 104` calls will be made to `inc`, `dec`, `getMaxKey`, and `getMinKey`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const AllOne = function() {
this.map = new Map()
}

AllOne.prototype.inc = function(key) {
let curCount
if (this.map.has(key)) {
curCount = this.map.get(key) + 1
} else {
curCount = 1
}
this.map.set(key, curCount)
}

AllOne.prototype.dec = function(key) {
if (this.map.has(key)) {
if (this.map.get(key) > 1) {
this.map.set(key, this.map.get(key) - 1)
} else this.map.delete(key)
} else {
return
}
}

AllOne.prototype.getMaxKey = function() {
let max = -Infinity,
maxStr = ''
for (let k of this.map) {
if (k[1] > max) {
max = k[1]
maxStr = k[0]
}
}
return maxStr
}

AllOne.prototype.getMinKey = function() {
let min = Infinity,
minStr = ''
for (let k of this.map) {
if (k[1] < min) {
min = k[1]
minStr = k[0]
}
}
return minStr
}
``````
Copy The Code &

Input

cmd
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

cmd
null, null, null, "hello", "hello", null, "hello", "leet"]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Node:
def __init__(self, key, value):
self.val = value
self.key = key
self.next = None
self.pre = None
class AllOne:

def __init__(self):
self.first = {}
self.last = {}
self.keys = {}
self.tail = Node(-1, -1)

node.pre = prev
node.next = prev.next
node.pre.next = node.next.pre = node

def remove(self, node):
node.pre.next = node.next
node.next.pre = node.pre

def process(self, node):
if self.last[node.val] == node and node.pre.val != node.val:
self.first.pop(node.val)
self.last.pop(node.val)
elif self.first[node.val] == node:
self.first[node.val] = node.next
elif self.last[node.val] == node:
self.last[node.val] = node.pre

def process2(self, node, prev, key, d):
if key in self.keys:
if node.val + d in self.last:
elif node.val in self.last:
else:
elif 1 in self.last:
node = Node(key, 0)
else:
node = Node(key, 0)
node.val += d
self.last[node.val] = node
if node.val not in self.first:
self.first[node.val] = node
if key not in self.keys:
self.keys[key] = node

def inc(self, key):
if key in self.keys:
node = self.keys[key]
prev = node.pre
self.process(node)
self.remove(node)
self.process2(node, prev, key, 1)
else:
self.process2(None, None, key, 1)

def dec(self, key):
if key in self.keys:
node = self.keys[key]
prev = node.pre
self.process(node)
self.remove(node)
if node.val != 1:
self.process2(node, prev, key, -1)
else:
self.keys.pop(key)

def getMaxKey(self):
return self.tail.pre.key if self.tail.pre != self.head else ""
def getMinKey(self):
``````
Copy The Code &

Input

cmd
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

cmd
null, null, null, "hello", "hello", null, "hello", "leet"]

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0432_AllOOneDataStructure
{
private Dictionary < string, Node> map;

public _0432_AllOOneDataStructure()
{
tail = new Node();

map = new Dictionary < string, Node>();
}

public void Inc(string key)
{
Node node = null;
if (map.ContainsKey(key))
node = map[key];
else

var next = node.next;
if (next.val != node.val + 1)
{
next = new Node(node.val + 1);
}
RemoveKey(key, node);
}

public void Dec(string key)
{
if (!map.ContainsKey(key)) return;

var node = map[key];
if (node.val == 1)
{
map.Remove(key);
RemoveKey(key, node);
return;
}

var prev = node.prev;
if (prev.val != node.val - 1)
{
prev = new Node(node.val - 1);
}

RemoveKey(key, node);
}

public string GetMaxKey()
{
if (tail.prev == head) return string.Empty;

return tail.prev.keys.First();
}

public string GetMinKey()
{
if (head.next == tail) return string.Empty;

}

private void AddNode(Node node, Node next)
{
next.next = node.next;
node.next.prev = next;

next.prev = node;
node.next = next;
}

private void RemoveNode(Node node)
{
node.prev.next = node.next;
node.next.prev = node.prev;
}

private void AddKey(string key, Node node)
{
}

private void RemoveKey(string key, Node node)
{
node.keys.Remove(key);
map.Remove(key);

if (node.keys.Count == 0)
RemoveNode(node);
}

public class Node
{
public HashSet < string> keys;
public Node next, prev;
public int val;

public Node(int val = 0)
{
this.val = val;
next = null;
prev = null;
keys = new HashSet < string>();
}
}
}

}
``````
Copy The Code &

Input

cmd
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

cmd
null, null, null, "hello", "hello", null, "hello", "leet"]