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.

&nbsp;
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"


&nbsp;
Constraints:


	1 &lt;= key.length &lt;= 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&nbsp;calls will be made to inc, dec, getMaxKey, and getMinKey.


from collections import defaultdict


class Set(object):

    def __init__(self):
        self._dict = {}
        self._list = []
        self._len = 0

    def add(self, v):
        if v in self._dict:
            pass
        else:
            self._list.append(v)
            self._dict[v] = self._len
            self._len += 1

    def __contains__(self, item):
        return item in self._dict

    def remove(self, v):
        if v not in self._dict:
            pass
        else:
            idx = self._dict[v]

            if idx < self._len - 1:
                self._list[idx] = self._list[-1]
                self._dict[self._list[idx]] = idx

            del self._dict[v]
            self._list.pop()
            self._len -= 1

    def __iter__(self):
        return iter(self._list)

    def check(self):
        assert len(self._dict) == len(self._list)
        for idx, key in enumerate(self._list):
            assert self._dict[key] == idx

    def __len__(self):
        return self._len

    def __repr__(self):
        return f"{self._dict}\n{self._list}"


class Node(object):

    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

    def set_prev(self, other_node):
        self.prev = other_node
        if other_node is not None:
            other_node.next = self

    def set_next(self, other_node):
        self.next = other_node
        if other_node is not None:
            other_node.prev = self

    def __repr__(self):
        return str(self.value)


class SortedKeyList(object):

    def __init__(self):
        self.head = Node(value=0)
        self.tail = Node(value=float("inf"))
        self.head.set_next(self.tail)

    def is_empty(self):
        return self.head.next is self.tail

    def min_key(self):
        if self.is_empty():
            return None
        else:
            return self.head.next.value

    def max_key(self):
        if self.is_empty():
            return None
        else:
            return self.tail.prev.value

    def incr_key(self, orig_node):
        orig_value = orig_node.value
        new_value = orig_value + 1
        next_node = orig_node.next
        if next_node.value == new_value:
            return self
        else:
            new_node = Node(new_value)
            new_node.set_prev(orig_node)
            new_node.set_next(next_node)
            return self

    def decr_key(self, orig_node):
        orig_value = orig_node.value
        new_value = orig_value - 1
        prev_node = orig_node.prev
        if prev_node.value == new_value:
            return self
        else:
            new_node = Node(new_value)
            new_node.set_next(orig_node)
            new_node.set_prev(prev_node)
            return self

    def delete_node(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.set_next(next_node)
        return self

    def __repr__(self):
        a = []
        node = self.head.next
        while True:
            if node is self.tail:
                break

            assert node.next.prev is node
            assert node.prev.next is node

            a.append(node.value)
            node = node.next
        return str(a)


class AllOne:

    def __init__(self):
        self.count_list = SortedKeyList()
        self.counter = defaultdict(lambda: self.count_list.head)
        self.keyed_by_count = defaultdict(set)

    def __repr__(self):
        return f"count_list={self.count_list}\ncounter={dict(self.counter)}\nkeyed_by_count={dict(self.keyed_by_count)}"

    def inc(self, key: str) -> None:
        orig_count_node = self.counter[key]
        orig_count = orig_count_node.value

        self.count_list.incr_key(orig_count_node)
        new_count_node = orig_count_node.next
        new_count = new_count_node.value
        assert new_count == orig_count + 1

        self.counter[key] = new_count_node

        if key in self.keyed_by_count[orig_count]:
            self.keyed_by_count[orig_count].remove(key)
        self.keyed_by_count[new_count].add(key)

        if len(self.keyed_by_count[orig_count]) == 0:
            del self.keyed_by_count[orig_count]
            if orig_count_node.value > 0:
                self.count_list.delete_node(orig_count_node)

    def dec(self, key: str) -> None:
        orig_count_node = self.counter[key]
        orig_count = orig_count_node.value

        self.count_list.decr_key(orig_count_node)
        new_count_node = orig_count_node.prev
        new_count = new_count_node.value
        assert new_count == orig_count - 1

        self.counter[key] = new_count_node

        if key in self.keyed_by_count[orig_count]:
            self.keyed_by_count[orig_count].remove(key)
        self.keyed_by_count[new_count].add(key)

        if new_count == 0:
            del self.counter[key]

        if len(self.keyed_by_count[orig_count]) == 0:
            del self.keyed_by_count[orig_count]
            self.count_list.delete_node(orig_count_node)

    def getMaxKey(self) -> str:
        max_count = self.count_list.max_key()
        if max_count is not None:
            return next(iter(self.keyed_by_count[max_count]))
        else:
            return ""

    def getMinKey(self) -> str:
        min_count = self.count_list.min_key()
        if min_count is not None:
            return next(iter(self.keyed_by_count[min_count]))
        else:
            return ""


def drive(m, p):
    s = AllOne()

    naive_counter = defaultdict(int)

    for method, param in zip(m, p):
        if method in ("inc", "dec"):
            word = param[0]

            if method == "inc":
                s.inc(word)
                naive_counter[word] += 1

            elif method == 'dec':
                s.dec(word)
                naive_counter[word] -= 1

            if naive_counter[word] == 0:
                del naive_counter[word]

            tmp_counter = defaultdict(set)
            for k, v in naive_counter.items():
                tmp_counter[v].add(k)

            sorted_keys = sorted(tmp_counter.keys())
            min_key = sorted_keys[0]
            max_key = sorted_keys[-1]

            if s.getMaxKey() not in tmp_counter[max_key]:
                print("Oh No!!!")
                return s, naive_counter, tmp_counter

            if s.getMinKey() not in tmp_counter[min_key]:
                print("Oh No!!!")
                return s, naive_counter, tmp_counter

    return None, None, None


if __name__ == '__main__':
    m = ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
    p = [[], ["hello"], ["hello"], [], [], ["leet"], [], []]
    s, naive_counter, tmp_counter = drive(m, p)
//Intuitions get from the top answer by @AaronLin1992
class AllOne {
    //Thoughts
    //inc() and dec() can be done with a Simple Map, but how do we getMaxKey() and getMinKey() in O(1)?
    //in order to get max and/or min on the fly, we need to maintain some kind of ordering so that we can always access max and min
    //to maintain some kind of ordering, the first thing we think about is arrays/lists, however, arrays/lists when insert and delete in the middle, it is O(N) operation
    //so instead, a linked list might work
    //as a result, we considering using Map(s) and LinkedList for our supporting data structures, details below
    
    private Map<String, Bucket> stringToBucket; //maps a string to bucket
    private Map<Integer, Bucket> countToBucket; //maps string count to bucket, note that because when we design this we can have multiple strings in a bucket, that makes it convenient so that for each count, we only need 1 bucket, thus the map data structure
    private BucketList bucketList;
    
    //first, we need to create a class for the LinkedList elements
    class Bucket {
        private Bucket prev;
        private Bucket next;
        
        private int count; //recording the count of instances
        private Set<String> keys; //note that we are using Set of Strings. The reason is because multiple Strings can have the same count and we want to put them in one bucket. This makes the problem easier to solve instead of putting them into different buckets.
        
        Bucket() {
            this.keys = new HashSet<>();
        }
        
        Bucket(String key) {
            this();
            this.count = 1;
            this.keys.add(key);
        }
        
    }
    
    //second, we need to create a linked list data structure of buckets
    class BucketList {
        private Bucket dummyHead; //the fake head before the real head //useful for getMinKey()
        private Bucket dummyTail; //the fake tail before the real tail //useful for getMaxKey()
        
        public BucketList() {
            dummyHead = new Bucket();
            dummyTail = new Bucket();
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }
        
        public Bucket createNewBucket(String key) {
            Bucket bucket = new Bucket(key);
            
            Bucket nextBucket = dummyHead.next;
            dummyHead.next = bucket;
            bucket.prev = dummyHead;
            nextBucket.prev = bucket;
            bucket.next = nextBucket;
            
            return bucket;
        }
        
        public Bucket createBucketToTheRight(Bucket fromBucket, String key, int count) {
            //initialize
            Bucket toBucket = new Bucket(key);
            toBucket.count = count;
            
            Bucket nextBucket = fromBucket.next;
            fromBucket.next = toBucket;
            toBucket.prev = fromBucket;
            nextBucket.prev = toBucket;
            toBucket.next = nextBucket;
            
            return toBucket;
        }
        
        public Bucket createBucketToTheLeft(Bucket fromBucket, String key, int count) {
            //initialize
            Bucket toBucket = new Bucket(key);
            toBucket.count = count;
            
            Bucket prevBucket = fromBucket.prev;
            prevBucket.next = toBucket;
            toBucket.prev = prevBucket;
            fromBucket.prev = toBucket;
            toBucket.next = fromBucket;
            
            return toBucket;
        }
        
        public boolean clean(Bucket oldBucket) {//clean bucket if bucket does not have any keys
            if (!oldBucket.keys.isEmpty()) {
                return false;
            }
            
            removeBucket(oldBucket);
            
            return true;
        }
        
        public void removeBucket(Bucket bucket) {
            Bucket prevBucket = bucket.prev;
            Bucket nextBucket = bucket.next;
            
            prevBucket.next = nextBucket;
            nextBucket.prev = prevBucket;
        }
    }
    

    public AllOne() {
        this.stringToBucket = new HashMap<>();
        this.countToBucket = new HashMap<>();
        this.bucketList = new BucketList();
    }
    
    public void inc(String key) {
        //first check if the string already present
        if (!stringToBucket.containsKey(key)) { //if not present 
            Bucket bucket = null;
            
            //check if there is count of 1 bucket already
            if (!countToBucket.containsKey(1)) { //if does not contain count of 1
                //we need to create a new bucket for count of 1 and add to the head (the minimum). Because count 1 should be the minimum exists in the bucket list
                bucket = bucketList.createNewBucket(key);
            } else { //if contains count of 1
                //then we just need to add the key to the bucket
                bucket = countToBucket.get(1);
                bucket.keys.add(key);
            }
            
            //don't forget to update the maps
            stringToBucket.put(key, bucket);
            countToBucket.put(1, bucket);
        } else { //if the key alreay present
            //first of all we need to get the current count for the key
            Bucket oldBucket = stringToBucket.get(key);
            Bucket newBucket = null;
            
            int count = oldBucket.count;
            count++; //increment 1
            //don't forget that we need to remove the key from existing bucket
            oldBucket.keys.remove(key);
            
            //now let's add the key with new count
            if (countToBucket.containsKey(count)) { //if there is already a bucket for this count
                //then just add to the set of keys
                newBucket = countToBucket.get(count);
                newBucket.keys.add(key);
            } else { //if there is no bucket for this count, create a new bucket, but where to place it? Ans: to the right of the old bucket
                newBucket = bucketList.createBucketToTheRight(oldBucket, key, count);     
            }
            
            //special scenario: if old bucket don't have any keys after removing the last key, then we need to remove the entire old bucket from the bucket list
            if (bucketList.clean(oldBucket)) {
                countToBucket.remove(oldBucket.count); //remove from map because the old bucket was removed
            }
            
            //don't forget to update the maps
            stringToBucket.put(key, newBucket);
            countToBucket.putIfAbsent(count, newBucket);
        }
    }
    
    public void dec(String key) {
        //since it is given that "It is guaranteed that key exists in the data structure before the decrement." we don't do additional validation for key exists here
        Bucket oldBucket = stringToBucket.get(key);
        Bucket newBucket = null;
        
        int count = oldBucket.count;
        count--; //decrement
        oldBucket.keys.remove(key);
        
        //special scenario - when count == 0
        if (count == 0) {
            stringToBucket.remove(key);
        } else {
            //now let's find a new bucket for the decremented count
            if (countToBucket.containsKey(count)) {//if there is already a bucket for the count
                newBucket = countToBucket.get(count);
                newBucket.keys.add(key);
            } else {//if there is no bucket for the count, then following similar logic as before, we need to add a bucket to the left of the existing bucket
                newBucket = bucketList.createBucketToTheLeft(oldBucket, key, count);
            }
            
            //don't forget to update the maps
            stringToBucket.put(key, newBucket);
            countToBucket.putIfAbsent(count, newBucket);
        }
        
        //special scenario: if old bucket don't have any keys after removing the last key, then we need to remove the entire old bucket from the bucket list
        if (bucketList.clean(oldBucket)) {
            countToBucket.remove(oldBucket.count); //remove from map because the old bucket was removed
        }
    }
    
    public String getMaxKey() {
        Set<String> maxSet = bucketList.dummyTail.prev.keys;
        
        return maxSet.isEmpty() ? "" : maxSet.iterator().next(); //if maxSet is empty, that means the bucketList don't have actual buckets
        
    }
    
    public String getMinKey() {
        Set<String> minSet = bucketList.dummyHead.next.keys;
        
        return minSet.isEmpty() ? "" : minSet.iterator().next(); //if minSet is empty, that means the bucketList don't have actual buckets
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */
class AllOne {
public:
    map<int,unordered_set<string>> minmax;
    unordered_map<string,int> count;
    AllOne() {
        
    }
    
    void inc(string key) {
         int was = count[key]++;
         if(was>0) {
             minmax[was].erase(key);
             if(minmax[was].size()==0) minmax.erase(was);
         }
         minmax[was+1].insert(key);
    }
    
    void dec(string key) {
         int was = count[key]--;
         minmax[was].erase(key);
         if(minmax[was].size()==0) minmax.erase(was);
         if(was-1==0) {
             count.erase(key);
         }else {
             minmax[was-1].insert(key);
         }
    }
    
    string getMaxKey() {
         return minmax.size() == 0 ? "" : *minmax.rbegin()->second.begin();
    }
    
    string getMinKey() { 
        return minmax.size() == 0 ? "" : *minmax.begin()->second.begin();
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */
var AllOne = function() {
  this.map = new Map();
  this.pre = '';
};

/** 
 * @param {set} map
 * @param {function} handler
 * @return {map}
 */
AllOne.prototype.sort = function(map, handler) {
  return new Map([...map].sort(handler));
};

/** 
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.inc = function(key) {
  this.map.set(key, this.map.get(key) + 1 || 1);
  this.pre = 'inc';
};

/** 
 * @param {string} key
 * @return {void}
 */
AllOne.prototype.dec = function(key) {
  this.map.get(key) == 1 ? this.map.delete(key) : this.map.set(key, this.map.get(key) - 1);
  this.pre = 'dec';
};

/**
 * @return {string}
 */
AllOne.prototype.getMaxKey = function() {
  if (this.pre != 'max') {
    this.map = this.sort(this.map, (a, b) => b[1] - a[1]);
  }
  this.pre = 'max';
  return this.map.keys().next().value || '';
};

/**
 * @return {string}
 */
AllOne.prototype.getMinKey = function() {
  if (this.pre != 'min') {
    this.map = this.sort(this.map, (a, b) => a[1] - b[1]);
  }
  this.pre = 'min';
  return this.map.keys().next().value || '';
};
All O`one Data Structure