C++, O(n), scan with a map
Intuition\nJust delete the rightmost occurrence of the min-char seen so far, when scanning the string from left to right.\n\n# Approach\nuse a map to maintain t
# Intuition\nJust delete the rightmost occurrence of the min-char seen so far, when scanning the string from left to right.\n\n# Approach\nuse a map to maintain the min char seen so far, with\nthe positions of its occurrences. \nSo that map is map<char, vector<int>>\n\n# Complexity\n- Time complexity:\nO(n * log 26) == O(n)\n\n- Space complexity:\nO(n + 26) == O(n)\n\n# Code\n```\n// Idea: always greedily delete the rightmost occurrence of \n// the min char seen so far.\n// use a map to maintain the min char seen so far, with\n// the positions of its occurrences.\nclass Solution {\npublic:\n    string clearStars(string s) {\n        // maps a unique char to the positions of its occurrences.\n        map<char, vector<int>> m; \n        // count of non-star chars seen so far.\n        // this variable can be deleted, as it\'s only for asserts.\n        int cnt = 0; \n        for (int i = 0; i < s.size(); ++i) {\n            const char c = s[i];\n            if (c == \'*\') {\n                // assert(cnt > 0);\n                // assert(!m.empty());\n                s[i] = \'-\';\n                auto iter = m.begin();\n                // assert(!iter->second.empty());\n                int pos = iter->second.back();\n                // delete the char\n                --cnt;\n                s[pos] = \'-\';\n                iter->second.pop_back();\n                if (iter->second.empty()) {\n                    m.erase(iter->first);\n                }\n            } else {\n                // maintain the cnt and the map\n                ++cnt;\n                m[c].push_back(i); // record its pos\n            }\n        }\n        string res;\n        for (char c : s) {\n            if (c != \'-\') {\n                res += c;\n            }\n        }\n        return res;\n    }\n};\n```
['C++']