Min heap with smallest (char + index) pairs.
Intuition and approach:\nQuestion wants me to delete chars from a string, first thing I think about is creating a stringbuilder because strings are immutable. \
# Intuition and approach:\nQuestion wants me to delete chars from a string, first thing I think about is creating a stringbuilder because strings are immutable. \n\nNow, even deleting from stringbuilder takes O(n) unless we remove from the end all the time(which we arent),\n\nso, instead of deleting, just replace the char with some non-alphabet like \'.\' \n\nWe can at the end, create a new stringbuilder by appending all the chars(except the \'.\') in this above mentioned stringbuilder to get the answer.\n\nGreat, now we just need to figure out how to delete the smallest alphabet on the left of *. The question says we can delete any smallest char occurence from the left of *. \n\nSo what now? Do we create possible permutations of such removals and then memoize them with backtracking along with pruning and sending a space shuttle to proxima centauri?\n\nNo, that will be going overboard. We need to make the smallest lexicographical(dictionary order) string.\n\nSo why would we remove the smallest index of that smallest character? Take for instance, acbasd* , if we remove first a, we get cbasd and if we remove the second a(closest to *), we get acbsd. \n\nWhich one is smaller lexicographically? Which one occurs in the dictionary first? acbsd or cbasd? It is acbsd. This illustrates we need to remove the "closest" to * or in other words, the biggest index of the said character.\n\nWe can start iterating from the beginning of our str. If we encounter \'*\' we now want to "delete" the closest smallest alphabet to its left. \n\nWe can simply just do that with a while loop, start iterating to its left and keep track of min char index. Once you have that index after reaching the 0 index, just set a \'.\' on that index. But this whole thing is O(n) operation at the worst case. \n\nWhich means, our total run time will be O(n^2). We look at the constraints, and figure we cant really do with this. It will likely give us TLE because 10^5 is the max len of the input string. 10^5^2 is 10^10 which is highly likely TLE.\n\nWe ask ourselves, why do I need to keep searching the same space again and again, can I somehow track the order in some auxillary data structure?\n\nThis is where minHeap comes into the picture.\n\nMin heap sorts the elements as it is inserting them. Creating an n sized heap takes n logn time because each insertion makes logn comparisons to bubble up the min element to the top.\n\nTo fetch the min element, we can poll the heap, which returns its top most element after removing it from the heap in logn again. It takes logn time again because the root is removed, it now has to figure out a new root by comparing the children at each level of the tree(heap), which has logn height.  \n\nSo now we create a min heap of int[] where int[] contains char(the ASCII val represented in int) at [0] and its index at [1]. We traverse our str, keep adding to the heap all the non *. It keeps getting sorted inherently....right? Not really.\n\nHeaps require a comparator to understand how we want to sort out the preexisting elements in it as we insert a new one(ore remove from it). For that, we create a comparator which takes both children nodes being compared (int[] a and int[] b) and call Integer.compare on their ASCII values. \n\nThis should work right? It wont. Lets say we have [a, 4] already inserted and [a, 1] as the new insertion.\n\n[a, 1] will actually get bubbled up to the top because we only told the program to compare char ASCII values, nothing about the index. While [a,1] is indeed the smallest char, it isnt the "closest" one to *. \n\nSo we need to be careful here and specify that we want to compare indices in case ASCII values are equal, and bubble the BIGGEST index to the top. \n\nGreat, so far so good. We have a heap that keeps increasing as we keep traversing the string with the smallest character closest to * on the top.\n\nWhenever we encounter *, we simply first set \'.\' to replace * and then we poll our heap which gives us the smallest char closest to the left of *. We will simply set a \'.\' over there as well. \n\nSo now is everything gucci? Wait...we are polling a heap, what if it has nothing to poll? What if we encounter a * before we got a chance to find alphabets? Or what if a series of **** is bigger than the current size of our heap?\n\nThat\'s a bummer, do we need to then do null checks here? That\'s a pain. Wait...lets read the description again. \n\nIt is guaranteed that  -->\nThe input is generated such that it is possible to delete all \'*\' characters.\n\nWe read this and first we thank our leetcode Gods that they showed kindness to us as they drive their lambo into the sunset while we have to grind problems on their website to afford basic housing. Then we move back to the problem.\n\nIn other words, there wont ever be * with no alphabets to its left, so our heap is ALWAYS non empty, meaning we can poll from it without worrying about NPEs(null pointer exceptions).\n\nThat\'s it, it should work. We\'ll just create an output string by appending all the non \'.\' \n   \n\n# Complexity\n- Time complexity: O(nlogn) : logn per insertion/removal, total n elements in the worst case. so n*logn total.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n) : heap and output string will hold n elements in the worst case(think no * in the input string at all), O(n+n) = O(2n) = O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public String clearStars(String s) {\n        StringBuilder str = new StringBuilder(s);\n        PriorityQueue<int[]> q = new PriorityQueue<>((int[] a, int[] b) -> {\n            int charComparison = Integer.compare(a[0], b[0]);\n            if (charComparison != 0) {\n                return charComparison;\n            }\n            // If characters are equal, compare their indices instead \n            // so pq doesnt bubble the wrong element to the top based on char alone\n            // we\'d want smallest char with the smallest index on the top. \n            return Integer.compare(b[1], a[1]); \n        });\n        for(int i = 0; i < str.length(); i++){\n            if(str.charAt(i) == \'*\'){\n                str.setCharAt(i, \'.\'); //removing *\n                int left = i-1;\n                //delete the closest left smallest non * by putting . there\n                int smallestLeftCharIndex = (q.poll())[1]; //logn operation\n                /********************************************************\n                * this would have given you TLE,                        *\n                * instead of polling pq, you\'re looking for the index   * \n                * which is O(n), making overall O(n^2)                  *\n                *********************************************************/\n                // char smallestLeftChar = \'Z\';\n                // int smallestLeftCharIndex = left;\n                // while(left >= 0){\n                //     char currLeftChar = str.charAt(left);\n                //     if(currLeftChar < smallestLeftChar){\n                //         smallestLeftChar = currLeftChar;\n                //         smallestLeftCharIndex = left;\n                //     }\n                //     left--;\n                // }\n                str.setCharAt(smallestLeftCharIndex, \'.\');\n                left--;\n                \n            }else{\n                //logn operation\n                //do it n times in the worst case, overall, O(nlogn)\n                q.add(new int[]{s.charAt(i), i});\n            }\n        }\n        StringBuilder ans = new StringBuilder();\n        for(int i = 0; i < str.length(); i++){\n            if(str.charAt(i) != \'.\'){\n                ans.append(str.charAt(i));\n            }\n        }\n        return ans.toString();\n    }\n}\n```
['String', 'Heap (Priority Queue)', 'Java']