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 "".
Trie? O(26)?
Heap + Map?
Yes. We can abstract these requirements as
- we can find key's value; string -> value; We can set a list for each value; and key point to a value level.
- if we need to inc or dec just move this key to next level
To use list, we can use .end, ++, -- to move the pointer in the list.also, we use a map to point to the list's iterator.
The reason why we need to store each key's count is that if we dec a key, we still know how many key in these count. If we do not store all the key in a count, we only store one element like 4 has a 'A', when we dec 'A', the value turn into 3, but whose value in the 4 we lose it.
if we let vector.begin()-- it will be the vector.end() (not exist)