Rightmost Smallest
For each star, we need to remove the rightmost instance of the smallest character.\n\nTo do that, we store positions of each character in pos as we go left to r
For each star, we need to remove the rightmost instance of the smallest character.\n\nTo do that, we store positions of each character in `pos` as we go left to right.\n\nWhen we see a star:\n- Find the smallest available character.\n\t- We can do it by iterating through 26 characters, or use a set or a heap.\n- Change the last position of that characer in `s` to `*`.\n- Remove the last position from `pos`.\n\nFinally, we remove all star characters, and return the string.\n\nThe complexity of this solution is O(26 n) for the simple iteration, and O(n log 26) for the set/heap.\n\nHowever, the runtime seems to favor the simple iteration:\n- Simple iteration: 80 ms\n- Set: 150 ms\n- Heap: 120 ms\n\nThis is, perhaps, because 26 is small enough number, and the set/heap add some overhead:\n\n### Simple Iteration\n**C++**\n```cpp\nstring clearStars(string s) {\n    array<vector<int>, 26> pos;\n    for (int i = 0; i < s.size(); ++i)\n        if (s[i] == \'*\')\n            for (auto &p : pos) {\n                if (!p.empty()) {\n                    s[p.back()] = \'*\';\n                    p.pop_back();\n                    break;\n                }\n            }\n        else\n            pos[s[i] - \'a\'].push_back(i);\n    erase(s, \'*\');\n    return s;\n}\n```\n\n### Set\n**C++**\n```cpp\nstring clearStars(string s) {\n    set<int> sm;\n    array<vector<int>, 26> pos;\n    for (int i = 0; i < s.size(); ++i)\n        if (s[i] == \'*\') {\n            while (pos[*begin(sm)].empty())\n                sm.erase(begin(sm));\n            s[pos[*begin(sm)].back()] = \'*\';\n            pos[*begin(sm)].pop_back();\n        }\n        else {\n            pos[s[i] - \'a\'].push_back(i);\n            sm.insert(s[i] - \'a\');\n        }\n\terase(s, \'*\');\n    return s;\n}\n```\n\n### Heap\n**C++**\n```cpp\nstring clearStars(string s) {\n    priority_queue<int, vector<int>, greater<int>> sm;\n    array<vector<int>, 26> pos;\n    for (int i = 0; i < s.size(); ++i)\n        if (s[i] == \'*\') {\n            while (pos[sm.top()].empty())\n                sm.pop();\n            s[pos[sm.top()].back()] = \'*\';\n            pos[sm.top()].pop_back();\n        }\n        else {\n            if (pos[s[i] - \'a\'].empty())\n                sm.push(s[i] - \'a\');\n            pos[s[i] - \'a\'].push_back(i);\n        }\n    erase(s, \'*\');\n    return s;\n}\n```
['C']