All O'One Data Structure Problem
Description
LeetCode Problem 432.
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 “”.
Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 * 10^4calls will be made to inc, dec, getMaxKey, and getMinKey.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class AllOne {
public:
map<string, int> mp;
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> mini;
priority_queue<pair<int, string>> maxi;
AllOne(){
}
void inc(string key) {
mp[key]++;
mini.push({mp[key], key});
maxi.push({mp[key], key});
}
void dec(string key) {
mp[key]--;
mini.push({mp[key], key});
maxi.push({mp[key], key});
}
string getMaxKey() {
while(maxi.size()){
if(maxi.top().first == mp[maxi.top().second] && mp[maxi.top().second]){
return maxi.top().second;
break;
}else{
maxi.pop();
}
}return "";
}
string getMinKey() {
while(mini.size()){
if(mini.top().first == mp[mini.top().second] && mp[mini.top().second]){
return mini.top().second;
break;
}else{
mini.pop();
}
}return "";
}
};
/**
* 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();
*/