[Python] - Storing indices in a heap
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to remove the most recent small character, so that lexicographically it will be
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to remove the most recent small character, so that lexicographically it will be small. If we remove the first small character from the beginning the string becomes lexicographically big.\nEx:\ns = \'aaba*\'\nHere the small character to the left of \'*\' is \'a\'. We have three a\'s at the indexes [0, 1, 3].\nIf we remove, \nat index - 0: \'aba\'\nat index - 1: \'aba\'\nat index - 3: \'aab\'\nSo, if we remove the character \'a\' at recent index, It would become lexicographically small.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse heap/priority queue to store the characters and their indices.\n```\nheapq.heappush(heap, (s[i], -i))\n``` \nStore the negative index, because heap gives us the smallest element first. Later use that index to mark the element of ans array to \'0\'.\n```python\ns = \'\'\nfor c in ans:\n    if c and c != \'*\': s += c\n```\nFinally to get the output string, join every character in the array except for the \'*\' and 0 values.\n\n# Complexity\n- Time complexity:\n$$O(nlogn)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```python\nclass Solution:\n    def clearStars(self, s: str) -> str:\n        heap, ans = [], []\n        i, n = 0, len(s)\n        while i < n:\n            if s[i] == \'*\':\n                el, index = heapq.heappop(heap)\n                ans[-index] = 0\n            else:\n                heapq.heappush(heap, (s[i], -i))\n            ans.append(s[i])\n            i += 1\n        s = \'\'\n        for c in ans:\n            if c and c != \'*\': s += c\n        return s\n```
['Array', 'String', 'Heap (Priority Queue)', 'Python3']