[Leetcode] 3170. Lexicographically Minimum String After Removing Stars

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

initial

honestly i think it is a v good heap question

So I thought wow its an easy question i just use heap and pop the lowest lexicographical alphabet whenever we see a "*"!

But if we have something like c*ed, correct answer is ed cuz the original order of string has to be preserved. But my approach was giving de cuz heap sorts it that way.

import heapq
class Solution:
    def clearStars(self, s: str) -> str:
        heap = []
        heapq.heapify(heap)
        flag=False
        for c in s:
            if c=='*':
                flag=True
                heapq.heappop(heap)
            else:
                heapq.heappush(heap,c)
        return "".join(heap) if  flag else s
        
        

sol

so how do we preserver the original roder? I thought about making bunch of flags and processing as a list but actually theres a much simpler way

What if we dont just join the heap as a string but when we iterate through the string in the first place, we mark the popped heap element's index in a deletedIndex set. Then, at the final iteration of string, when we see that current element is not * and current index is not in that deletedIndex set, that means it is a valid character to be appended to our answer string.

also, v impt that the pattern is popping the lowest lexicographical alphabet at the right most index. So if we have aba*c, We need to pop the second a, not the first a to get the right answer. Right answer should be abc, not bac.

So we append minus index to the heap as the second element, and reverse that minus index when adding that index to our deleteIndex set.

import heapq
class Solution:
    def clearStars(self, s: str) -> str:
        heap = []
        heapq.heapify(heap)
        ans=""
        flag=False
        deleteIndex=set()
        for i,c in enumerate(s):
            if c=='*':
                flag=True
                c,idx = heapq.heappop(heap)
                deleteIndex.add(-idx)
            else:
                heapq.heappush(heap,(c,-i))
        for i,c in enumerate(s):
            if i not in deleteIndex and c!='*':
                ans+=s[i]
        return ans

complexity

n log n time? cuz outer loop is n but heap operations are log n. Yep thats correct
n space