Python3 Dictionary solution
Intuition\n Describe your first thoughts on how to solve this problem. \nBrute force solution is O(n^2), so we have to do better. We notice that, whenever there
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBrute force solution is O(n^2), so we have to do better. We notice that, whenever there are multiple occurrences of the "minimum letter", we always remove the rightmost one (guarantees the lexically least string after removal). So, we can store characters and the indexes at which we saw them. Whenever we see an asterisk, simply remove the rightmost occurrence of the minimum letter. Once we have iterated through the string, we just need to reconstruct the string using only the letters that we didn\'t remove.\n\n# Complexity\n- Time complexity:$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def clearStars(self, s: str) -> str:\n        chars = {}\n        for i in range(len(s)):\n            if s[i] != "*":\n                # store the letter\n                if s[i] not in chars:\n                    chars[s[i]] = []\n\n                chars[s[i]].append(i)\n\n            else:\n                # it\'s a star\n                # find minimum letter so far\n                min_letter = min(chars.keys())\n                # we will remove that letter\n                chars[min_letter].pop()  # remove the rightmost one\n\n                # remove letter if it no longer occurs\n                if len(chars[min_letter]) == 0:\n                    del chars[min_letter]\n\n        # reconstruct string\n        reconstructed = ["" for _ in range(len(s))]\n        for letter in chars:\n            for idx in chars[letter]:\n                reconstructed[idx] = letter\n        return "".join(reconstructed)\n```
['Python3']