C++ | Easy to Understand | Step By Step Expl
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to remove asterisks (\'\') from a string while preserving the
![Zombie Upvote.png](https://assets.leetcode.com/users/images/46981039-92a0-4676-8a5c-8be857ac654d_1717300873.1417475.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to remove asterisks (\'*\') from a string while preserving the lexicographically smallest possible result. We can achieve this by iterating through the string and considering two cases:\n\n1. **Non-asterisk character (s[i] != \'*\'):**\n    - We add the character and its index to a priority queue (pq). Here, the priority is defined such that characters with the same value are ordered with larger indices coming first (ensuring we remove the rightmost occurrence if necessary). When a smaller character is encountered later, it will take precedence in the queue.\n2. **Asterisk character (s[i] == \'*\'):**\n    - We remove the leftmost non-asterisk character from the queue using pq.top(). This character represents the smallest non-asterisk encountered so far, and we mark its position in the string with another asterisk (s[it.second] = \'*\'), effectively deleting it.\nBy systematically removing the leftmost asterisk and the smallest non-asterisk character to its left, we gradually transform the string into the lexicographically smallest form without asterisks.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Priority Queue:** We employ a priority queue (pq) to store pairs of characters and their corresponding indices. The prioritization criteria are:\n    - If characters are the same, the pair with the larger index has higher priority (ensuring rightmost non-asterisk characters are considered first).\n   - If characters are different, characters with a smaller value have higher priority (guaranteeing the removal of the smallest non-asterisk character).\n2. **Iterate and Process: We iterate through the string (s):**\n   - **If the current character is not an asterisk (s[i] != \'*\'):**\n       - Push the character-index pair ({s[i], i}) onto the priority queue.\n   - **If the current character is an asterisk (s[i] == \'*\'):**\n       - Pop the top element (it) from the priority queue. This represents the smallest non-asterisk character encountered so far.\n       - Mark the position of this character in the string with another asterisk (s[it.second] = \'*\'), effectively deleting it.\n       \n3. **Remove Asterisks:** After processing the entire string, we use std::remove to remove all remaining asterisks from s.\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#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    string clearStars(string s) {\n        int n = s.size();\n        \n        // PQ to store pairs (character, index)\n        // Custom to get smallest character but largest index\n        auto comp = [](const pair<char, int>& a, const pair<char, int>& b) {\n            if (a.first == b.first) {\n                return a.second < b.second; // larger index pehle ayega\n            }\n            return a.first > b.first; // smaller character pehle ayega\n        };\n        \n        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(comp)> pq(comp);\n\n\n        for (int i = 0; i < n; ++i) {\n            if (s[i] != \'*\') {\n                pq.push({s[i], i});\n            } else {\n                auto it = pq.top();\n                pq.pop();\n                s[it.second] = \'*\';\n            }\n        }\n\n        s.erase(std::remove(s.begin(), s.end(), \'*\'), s.end());\n        \n        return s;\n    }\n};\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['String', 'Heap (Priority Queue)', 'C++']