Easy to Understand | using Priority queue🔥✅ | No Custom Comparator
Approach\n\n\nIn this problem, we need to remove characters from a string s whenever a * is encountered. Specifically, each * character should remove the smalle
# Approach\n\n\nIn this problem, we need to remove characters from a string `s` whenever a `*` is encountered. Specifically, each `*` character should remove the smallest character that appears before it. If there are multiple smallest characters, we remove the nearest one to the `*`.\n\nTo solve this, we can use a min-heap (priority queue) to efficiently manage the characters and their positions in the string. Here is a step-by-step guide to understanding and implementing the solution:\n\n### Step-by-Step Solution\n\n1. **Min-Heap Usage**:\n    - We use a min-heap to keep track of characters and their positions. By storing the positions as negative values, we can ensure that the most recent occurrence of the smallest character is prioritized when popping from the heap.\n\n2. **First For-Loop**:\n    - Traverse the string `s`.\n    - For each non-star character, push it onto the min-heap along with its position (multiplied by -1).\n    - For each \'*\' character, pop the top element from the min-heap. This removes the smallest character that appears closest to the \'*\'.\n\n3. **Maintaining Valid Indices**:\n    - After processing the entire string, the min-heap will contain only the characters that have not been removed by any \'*\'.\n    - Transfer the indices of these remaining characters into a set (`validIndices`). This set helps us quickly check which characters should be included in the final result.\n\n4. **Second For-Loop**:\n    - Traverse the string `s` again.\n    - Construct the result string by including only those characters whose indices are present in the `validIndices` set.\n\n### Example Walkthrough\n\nLet\'s consider an example string `s = "abc*de*f*g"`:\n\n1. **Initial Traversal and Min-Heap Operations**:\n    - \'a\' is added to the min-heap.\n    - \'b\' is added to the min-heap.\n    - \'c\' is added to the min-heap.\n    - \'*\' is encountered, the smallest character (\'a\') is removed from the min-heap.\n    - \'d\' is added to the min-heap.\n    - \'e\' is added to the min-heap.\n    - \'*\' is encountered, the smallest character (\'b\') is removed from the min-heap.\n    - \'f\' is added to the min-heap.\n    - \'*\' is encountered, the smallest character (\'c\') is removed from the min-heap.\n    - \'g\' is added to the min-heap.\n\n2. **Final State of the Min-Heap**:\n    - The min-heap now contains \'d\', \'e\', \'f\' and \'g\'.\n\n3. **Transfer to Set**:\n    - The set `validIndices` will have the indices corresponding to \'d\', \'e\', \'f\' and \'g\' (i.e., 4, 5,7 and 9).\n\n4. **Constructing the Result String**:\n    - Traverse `s` again and include only those characters whose indices are in `validIndices`.\n    - The final result is `"defg"`.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: `O(nlogn)`\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```\nclass Solution {\npublic:\n    string clearStars(string s) {\n        priority_queue<pair<char, int>, vector<pair<char, int>>, greater<pair<char, int>>> charQueue; \n        for (int i = 0; i < s.size(); i++) {\n            if (s[i] != \'*\') {\n                charQueue.push({s[i], -i}); \n            } else if (s[i] == \'*\') {\n                charQueue.pop();\n            }\n        }\n        \n        set<int> validIndices;\n        while (!charQueue.empty()) {\n            validIndices.insert(-charQueue.top().second);\n            charQueue.pop();\n        }\n        \n        string result = "";\n        for (int i = 0; i < s.size(); i++) {\n            if (validIndices.count(i)) {\n                result += s[i];\n            }\n        }\n        \n        return result;\n    }\n};\n\n```
['String', 'Heap (Priority Queue)', 'C++']