Code Using a Custom Class Comparator inside an Ordered Set in C++
Approach\nFor getting lexicographically smallest string the main logic is to delete that smallest character which is left to a \'\' character which has greatest
# Approach\nFor getting lexicographically smallest string the main logic is to delete that smallest character which is left to a \'*\' character which has greatest index.\n\n# Complexity\n- Time complexity: $$O(n*log(n))$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\ntemplate <typename T>\nclass comp{\n    public:\n    bool operator()(T a, T b) const {\n        if(a.first == b.first) return a.second > b.second;\n        return a.first < b.first;\n    }\n};\nclass Solution {\npublic:\n    string clearStars(string s) {\n        int n = s.size();\n        vector<pair<char,int>> arr;\n        set<pair<char,int>,comp<pair<char,int>>> st;\n        for(int i=0;i<n;i++){\n            if(s[i] == \'*\'){\n                arr.push_back(*st.begin());\n                st.erase(st.begin());\n            }\n            else{\n                st.insert({s[i],i});\n            }\n        }\n        vector<int> idx;\n        string ans = "";\n        for(auto item : arr){\n            idx.push_back(item.second);\n        }\n        int p = 0;\n        sort(idx.begin(),idx.end());\n        for(int i=0;i<n;i++){\n            if(s[i] == \'*\') continue;\n            if(p<idx.size() and idx[p] == i){\n                p++;\n            }\n            else{\n                ans+=s[i];\n            }\n        }\n        return ans;\n    }\n};\n```
['Sorting', 'Ordered Set', 'C++']