Easy Map+SetImplementation💯⭐
Clear Stars from String\n\n## Problem Statement\n\nGiven a string s containing lowercase letters and the \'*\' character, remove the character just before each 
# Clear Stars from String\n\n## Problem Statement\n\nGiven a string `s` containing lowercase letters and the `\'*\'` character, remove the character just before each `\'*\'` along with the `\'*\'` itself and return the final string.\n\n## Intuition\n\nTo solve this problem, we need to keep track of characters that are valid (i.e., not removed due to a `\'*\'` character). A priority queue can help us maintain the order of characters efficiently as we process the string.\n\n## Approach\n\n1. Traverse the string.\n2. Use a priority queue to store non-star characters along with their negative indices (to simulate max-heap behavior with a min-heap).\n3. When encountering a `\'*\'`, pop the top of the priority queue, effectively removing the most recently added non-star character.\n4. Collect the valid indices from the priority queue into a set.\n5. Construct the final string by including only the characters at valid indices.\n\n## Complexity\n\n- **Time complexity:** \\(O(n \\log n)\\) due to the operations involving the priority queue.\n- **Space complexity:** \\(O(n)\\) for storing the valid indices and the priority queue.\n\n## Code\n\n```cpp\nclass Solution {\npublic:\n    string clearStars(string s) {\n        priority_queue<pair<char, int>, vector<pair<char, int>>, greater<pair<char, int>>> pq; \n\n        for (int i = 0; i < s.size(); i++) {\n            if (s[i] != \'*\') {\n                pq.push({s[i], -i}); \n            } else if (s[i] == \'*\') {\n                pq.pop();\n            }\n        }\n\n        set<int> validIndices;\n        while (!pq.empty()) {\n            validIndices.insert(-pq.top().second);\n            pq.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
['Heap (Priority Queue)', 'Ordered Set', 'C++']