# https://leetcode.com/problems/lexicographically-minimum-string-after-removing-stars

import heapq

class Solution:
    def clearStars(self, s: str) -> str:
        result = list(s)
        h = []
        for i in range(len(s)):
            if s[i] == '*':
                (_, _, origin) = heapq.heappop(h)
                result[origin] = ''
                result[i] = ''
            else:
                heapq.heappush(h, (s[i], -i, i))
        return ''.join(result)