3170. Lexicographically Minimum String After Removing Stars

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', do the following operation:

• Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

class Solution {
public:
    string clearStars(string s) {
        map<char,vector<int>> mp;
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '*') {
                if(mp.size()) {
                    begin(mp)->second.pop_back();
                    if(begin(mp)->second.empty()) mp.erase(begin(mp));
                }
            } else mp[s[i]].push_back(i);
        }
        vector<pair<int,char>> S;
        for(auto& [ch, ord] : mp) {
            for(auto& p : ord) S.push_back({p,ch});
        }
        sort(begin(S), end(S));
        string res = "";
        for(auto& [_,ch] : S) res.push_back(ch);
        return res;
    }
};