Simply Explained Python Solution - Priority Queue and Heap
This question is kind of tricky. Every * means that we must remove a letter that is to its left. Not only that, but the removed letter has to be the smallest on
This question is kind of tricky. Every `*` means that we must remove a letter that is to its left. Not only that, but the removed letter has to be the *smallest* one to its left, and also we must return the *lexicographically smallest solution*.\n\nSo, how do we do this?\n\nLet\'s work it out.\n\nIf we iterate through the string and check to the left of every `*`, it\'s going to cost us a lot of precious time.\n\nIn addition, we need the lexicographically smallest string. This means that when we sort a pool of all possible solutions by alphabetical order, what we return must be the first. We can achieve this by removing the *rightmost* letter that we can. By this, I mean that if we take the testcase `aaba*`, we remove the third "a", and by doing this, we get `aab`. The other possible solutions are both `aba`, which is lexicographically *larger* than `aab`.\n\nWhat we could do is to have two variables to track the index and value of a character. If we encounter a character that is smaller or the same as the previous smallest character we encountered, we replace both variables with new values. This guarantees the character we store when we encounter our next `*` can be removed to create the lexicographically smallest output, but there is a huge problem behind this.\n\nTake the testcase `aaba**`. This testcase requires you to now either go over the  entire list again, or to store a *second* character value! The testcase `aaba***` requires you to store *three*! Going over the list again requires too much time, so we *must* store the characters.\n\nWouldn\'t it be great if we had a datatype similar to a list, but whenever we put something in it, it sorts itself?\n\nWe have something like that! It\'s called a **priority queue**.\n\nIn Python, we can use the heap to implement a priority queue. This uses the heapq library.\n\nWhen we encounter a letter, we put it into the priority queue, which sorts the character by its value and index. Then, when we see a `*`, we can just pull the smallest character with the largest index out of the priority queue, and then remove it from the string.\n\n```\nimport heapq\nclass Solution:\n    def clearStars(self, s: str) -> str:\n        # r is the list of indices to remove at the end\n        r = set()\n        # creates priority queue\n        sm = []\n        heapq.heapify(sm)\n        for i, v in enumerate(s):\n            # Takes something from our heap if we face a "*"\n            if v == "*":\n                # marks what indices to remove at the end\n                r.add(i)\n                r.add(-heapq.heappop(sm)[1])\n            else:\n                # Otherwise, adds the character to our heap\n                # Heap is smallest out first\n                # This is good for our character, but not for the index\n                # So, we make larger indices smallest by negation\n                heapq.heappush(sm, (v, -i))\n        # If it should be removed, don\'t include it in the string we return\n        return "".join(s[i] for i in range(len(s)) if i not in r)\n```
['Python3']