O(n) solution optimized!!
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n\n# Complexity\n- Tim
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nworest case: O(3n) - if  s consists of only \'*\'\nO(3n) = O(n)  hence the overall time complexity is O(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution:\n    def clearStars(self, s: str) -> str:\n\n        # index is a dictionry that stores the index of each character seen \n        index = defaultdict(list)\n        ast_index = []   # ast_index is used to store index of "*" seen \n        deleted = set()\n        \n        for i, char in enumerate(s): \n            \n            if char != \'*\': \n                index[char].append(i)\n            else: \n                if ast_index: \n                    deleted.add(ast_index.pop())\n                \n                if index: \n                    small = min(index)\n                    \n                    deleted.add(index[small].pop())\n                    \n                    if not index[small]: \n                        del index[small]\n                    \n                ast_index.append(i)\n        \n    \n        stack = []\n        for i in range(len(s)): \n            \n            if s[i] != \'*\' and i not in deleted: \n                stack.append(s[i])\n                \n        return \'\'.join(stack)\n                    \n        \n```
['Python3']