class AllOne:
    def __init__(self):
        self.counts = {} #str -> number of instances
        self.strings = {} #number of instance -> set of strings
        self.max = 0 # number of max instances of a string in counts 
        self.min = 0 # number of min instances of a string in counts 
        
    def inc(self, s: str) -> None:
        if s in self.counts:
            # update self.min and self.max
            if s in self.strings[self.max]:
                self.max +=1
            self.strings[self.counts[s]].remove(s)
            if self.strings[self.min] == set(): # then s was the unique min val
                self.min += 1

            # update self.strings and self.counts
            if self.strings[self.counts[s]] == set():
                del self.strings[self.counts[s]]
            self.counts[s] += 1
            if self.counts[s] in self.strings:
                self.strings[self.counts[s]].add(s)
            else:
                self.strings[self.counts[s]] = {s}

        else:
            if self.min == 0: # no strings so far
                self.max = 1
            self.min = 1
            
            self.counts[s] = 1
            if 1 in self.strings:
                self.strings[1].add(s)
            else: 
                self.strings[1] = {s}

    def dec(self, s: str) -> None:
        self.strings[self.counts[s]].remove(s)
        if self.strings[self.max] == set(): #removed only max val
            self.max -= 1
        if self.counts[s] == self.min:
            self.min -= 1

        if self.strings[self.counts[s]] == set():
                del self.strings[self.counts[s]]
        if self.min == 0 and self.strings != {}:
            empty = True
            i=1
            while empty:
                if i in self.strings:
                    self.min = i
                    empty = False
                i += 1
            
        self.counts[s] -= 1
        if self.counts[s] == 0:
            del self.counts[s]

        else:
            if self.counts[s] in self.strings:
                self.strings[self.counts[s]].add(s)
            else:
                self.strings[self.counts[s]] = {s}
                
        
    def getMaxKey(self) -> str:
        if self.max == 0:
            return ""
        else:
            return next(iter(self.strings[self.max]))
            
    def getMinKey(self) -> str:
        if self.min == 0:
            return ""
        else:
            return next(iter(self.strings[self.min]))

allOne = AllOne()
allOne.inc("hello")
allOne.inc("hello")
print(allOne.getMaxKey())
print(allOne.getMinKey())
allOne.inc("leet")
print(allOne.getMaxKey())
print(allOne.getMinKey())
# hello hello hello leet

hello
hello
hello
leet