Detailed Explanation for Multiple Approaches.
Intuition\n Describe your first thoughts on how to solve this problem. \n\nIn this problem, we are asked to:\n\n1. Remove smallest character in the left side of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nIn this problem, we are asked to:\n\n1. Remove ***smallest*** character in the left side of `*`.\n2. Get **lexicographically minimum string** possible from the operations.\n\nThus, we need to do **deletion of right-most occurence of smallest character that appears in the left side of `*` in the string**.\n\nSmallest character is about the alphabetic order (a, b, c, d, e, ..., y, z). For example, if we have string `aac*ad*`, then we will do:\n\n1. First `*` appears as 4th character in the string, so we need to remove **rightmost** of **smallest** character before `*` and the `*` from `aac*`, which results `ac`.\n2. Second `*` is at the end of string, then we remove the leftmost `a` from the string `acad*`. Hence, the final result is `acd`.\n\nSo, there are 2 ways to address this problem:\n\n1. Priority Queue\n2. Hash Table + Stack\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n## Priority Queue\n\nWith this container, we can simply get the character to delete every time we encounter `*`. The priority for comparation is:\n\n1. Smallest character in alphabet order.\n2. Biggest index (most recent) of occurences of that character in the string.\n\nPseudocode:\n1. Initialize a priority queue of `pair<char, int>` (pair of char and its occurence, or create a class implementing `Comparable` in Java)  with the priority above. \n2. For every character in string `s`:\n    1. If `s[i] == \'*\'`, pop from priority queue.\n    2. Otherwise, push the `<s[i], i>` to priority queue.\n3. Create container for answer with the size of `s`.\n4. For every remaining elements of priority queue, assign the char to their indexes.\n    ```\n    while(!pq.isEmpty())\n        ans[pq.top().i] = pq.pop().ch\n    ```\n5. Return the answer. You may need to replace the initialized `\\0` to empty string.\n\n### Example (s = `aac*ad*`)\n\nIn this example, `pq` is the priority queue and top if the left most element.\n\n1. ```\n    i = 0, s[i] = \'a\' // push <\'a\', 0>\n    pq = [<\'a\', 0>]\n    ```\n1. ```\n    i = 1, s[i] = \'a\' // push <\'a\', 1>\n    pq = [<\'a\', 0>, <\'a\', 1>]\n    ```\n1. ```\n    i = 2, s[i] = \'c\' // push <\'c\', 2>\n    pq = [<\'a\', 0>, <\'a\', 1>, <\'c\', 2>]\n    ```\n1. ```\n    i = 3, s[i] = \'*\' // pop\n    pq = [<\'a\', 0>, <\'c\', 2>]\n    ```\n1. ```\n    i = 4, s[i] = \'a\' // push\n    pq = [<\'a\', 4>, <\'a\', 0>, <\'c\', 2>]\n    ```\n1. ```\n    i = 5, s[i] = \'d\' // push\n    pq = [<\'a\', 4>, <\'a\', 0>, <\'c\', 2>, <\'d\', 5>]\n    ```\n1. ```\n    i = 6, s[i] = \'*\' // pop\n    pq = [<\'a\', 0>, <\'c\', 2>, <\'d\', 5>]\n    ```\n1. Reconstruct the string, so it will be `acd` as final answer.\n\n## Hash Table + Stack\n\nThe idea is to store occurences from all characters in the string until we find `*` (Hash Map / Table) and do removal based on the latest element found (last-in-first-out / Stack). \n\nSteps:\n\n1. Initialize a `Map<Character, Stack<Integer>>` container, let\'s name it `m`.\n2. For every character in string `s`:\n    1. If current char `s[i] == \'*\'`:\n        1. Get existing smallest alphabetic character occurence stack from `m`, and pop it out.\n    2. Otherwise, push the occurence index `i` to the stack in `m[s[i]]`. You may need to create new Stack for `s[i]` if it doesn\'t exist in `m`.\n2. For every remaining elements of m, assign the char to their indexes.\n    ```\n    for key in m.keys():\n        while m[key] is not empty():\n            ans[m[key].pop()] = key\n    ```\n2. Return the answer. You may need to replace the initialized `\\0` to empty string.\n\n### Example (s = `aac*ad*`)\n\nIn this example, the stack is represented by `[]` and top of stack is at the rightmost, before `]`.\n\n1. ```\n    i = 0, s[i] = \'a\' // push 0\n    m = {\'a\': [0]}\n    ```\n1. ```\n    i = 1, s[i] = \'a\' // push 1\n    m = {\'a\': [0, 1]}\n    ```\n1. ```\n    i = 2, s[i] = \'c\' // push 2\n    m = {\'a\': [0, 1], \'c\': [2]}\n    ```\n1. ```\n    i = 3, s[i] = \'*\' // pop\n    m = {\'a\': [0], \'c\': [2]}\n    ```\n1. ```\n    i = 4, s[i] = \'a\' // push\n    m = {\'a\': [0, 4], \'c\': [2]}\n    ```\n1. ```\n    i = 5, s[i] = \'d\' // push\n    m = {\'a\': [0, 4], \'c\': [2], \'d\': [5]}\n    ```\n1. ```\n    i = 6, s[i] = \'*\' // pop\n    m = {\'a\': [0], \'c\': [2], \'d\': [5]}\n    ```\n1. Reconstruct the string, so it will be `acd` as final answer.\n\n# Complexity\n- Time complexity: $$O(n log( n))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n## Priority Queue\n\n```Java []\nclass Solution {\n    class Char implements Comparable<Char>{\n        char c;\n        int occ;\n\n        public Char(char c, int occ) {\n            this.c = c;\n            this.occ = occ;\n        }\n        \n        @Override\n        public int compareTo(Char that) {\n            return this.c - that.c == 0 ? that.occ - this.occ : this.c - that.c; \n        }\n    }\n    public String clearStars(String s) {\n        PriorityQueue<Char> pq = new PriorityQueue();\n        for(int i=0; i<s.length(); i++) {\n            if(s.charAt(i) == \'*\') {\n                pq.poll();\n            } else {\n                pq.offer(new Char(s.charAt(i), i));\n            }\n        }\n        char[] ans = new char[s.length()];\n        while(!pq.isEmpty()) {\n            ans[pq.peek().occ] = pq.poll().c;\n        }\n        return new String(ans).replaceAll("\\0", "");\n    }\n}\n```\n```c++ []\n#define mp(a, b) make_pair(a, b)\ntypedef pair<char, int> pci;\n\nclass Solution {\npublic:\n    string clearStars(string s) {\n        auto Compare = [](pci &a, pci &b) {\n            return a.first == b.first ? a.second < b.second : a.first > b.first;\n        };\n        priority_queue<pci, vector<pci>, decltype(Compare)> pq;\n        for(int i=0; i<s.length(); i++) {\n            if(s[i] == \'*\') {\n                pci p = pq.top();\n                s[p.second] = \'*\';\n                pq.pop();\n            } else {\n                pq.push(mp(s[i], i));\n            }\n        }\n        string ans = "";\n        for(int i=0; i<s.length(); i++) {\n            if(s[i] != \'*\') {\n                ans += s[i];\n            }\n        }\n        return ans;\n    }\n};\n```\n\n## Hash Table + Stack\n\n```Java []\nclass Solution {\n    public String clearStars(String s) {\n        Map<Character, Stack<Integer>> m = new HashMap();\n        for(int i=0; i<s.length(); i++) {\n            char c = s.charAt(i);\n            if(c == \'*\') {\n                for(char ch = \'a\'; ch <= \'z\'; ch++) {\n                    if(m.get(ch) != null && !m.get(ch).isEmpty()){\n                        m.get(ch).pop();\n                        break;\n                    }\n                }\n            } else {\n                if(!m.containsKey(c))\n                    m.put(c, new Stack());\n                m.get(c).push(i);\n            }\n        }\n        char[] ans = new char[s.length()];\n        for(Map.Entry<Character, Stack<Integer>> e : m.entrySet()) {\n            while(!e.getValue().isEmpty())\n                ans[e.getValue().pop()] = e.getKey();\n        }\n        return new String(ans).replaceAll("\\0", "");\n    }\n}\n```
['Hash Table', 'Stack', 'Heap (Priority Queue)', 'Java']