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 <= 10key consists of lowercase English letters.dec, key is existing in the data structure.5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.class AllOne {
private class Node {
int freq;
Node prev;
Node next;
Set<String> words;
Node(int freq, Node prev, Node next) {
this.freq = freq;
this.prev = prev;
this.next = next;
words = new HashSet<>();
}
}
Map<String, Node> allO1;
Node head;
Node tail;
public AllOne() {
allO1 = new HashMap<>();
head = new Node(1, null, null);
tail = head;
}
public void inc(String key) {
if (allO1.containsKey(key)) { // indicates its current tail node
Node curr = allO1.get(key);
Node newNode = curr.next;
if (newNode == null) {
newNode = new Node(curr.freq + 1, curr, null);
curr.next = newNode;
tail = newNode;
} else if (newNode.freq > curr.freq + 1) {
newNode = new Node(curr.freq + 1, curr, curr.next);
curr.next.prev = newNode;
curr.next = newNode;
}
newNode.words.add(key);
curr.words.remove(key);
if (curr != head && curr.words.isEmpty()) { // if oldNode has no words, purge it
curr.prev.next = newNode;
newNode.prev = curr.prev;
}
allO1.put(key, newNode);
} else {
head.words.add(key);
allO1.put(key, head);
}
}
public void dec(String key) {
Node curr = allO1.get(key);
Node newNode = curr.prev;
if (newNode == null) { // indicates past freq was 1
allO1.remove(key);
newNode = head;
} else if (newNode.freq < curr.freq - 1) {
newNode = new Node(curr.freq - 1, curr.prev, curr);
curr.prev.next = newNode;
curr.prev = newNode;
allO1.put(key, newNode);
} else {
newNode.words.add(key);
allO1.put(key, newNode);
}
curr.words.remove(key);
if (curr.words.isEmpty()) { // if oldNode has no words, purge it
newNode.next = curr.next;
if (curr != tail)
curr.next.prev = newNode;
else
tail = newNode;
}
}
public String getMaxKey() {
if (tail == null)
return "";
Iterator<String> itr = tail.words.iterator();
return itr.hasNext() ? itr.next() : "";
}
public String getMinKey() {
Node curr = head.words.isEmpty() ? head.next : head;
if (curr == null)
return "";
Iterator<String> itr = curr.words.iterator();
return itr.hasNext() ? itr.next() : "";
}
}
/**
* 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();
*/