Easy HashMap and HashSet Solution
IntuitionApproachComplexity
Time complexity:
O(nlogn)
Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(nlogn)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
int n;
int findSmallestChar(int &curr_idx,vector<int> &vec,unordered_map<int,set<int>> &mp){
    int ch;
    for(int i=0;i<26;i++){
        if(vec[i] > 0){
            set<int> &freq = mp[i];
            if(*freq.begin() < curr_idx){
                vec[i]--;
                return i;
            }
        }
    }
    return -1;
}
    string clearStars(string s) {
        n = s.length();
        int last_idx = -1;
        for(int i=0;i<n;i++){
            if(s[i] == '*') last_idx = i;
        }
        if(last_idx == -1) return s;
        vector<int> vec(26,0);
        unordered_map<int,set<int>> mp;
        for(int i=0;i<n;i++){
            if(s[i] != '*'){
                vec[s[i]-'a']++;
                mp[s[i]-'a'].insert(i);
            }
        }
        for(int i=0;i<n;i++){
           if(i > last_idx) break;
           if(s[i] == '*'){
            int ch = findSmallestChar(i,vec,mp);
            set<int> &st = mp[ch];
            auto it = st.lower_bound(i);
            it--;
            st.erase(*it);
           }
        }
        vector<vector<int>> v;
        for(auto &it : mp){
            set<int> &st = it.second;
            for(auto &itr : st){
                v.push_back({itr,it.first});
            }
        }
        sort(v.begin(),v.end());
        string result = "";
        int m = v.size();
        for(int i=0;i<m;i++){
            char ch = v[i][1] + 'a';
            result += ch;
        }
        return result;
    }
};
```
['C++']