316. Remove Duplicate Letters - cocoder39/coco39_LC GitHub Wiki

string removeDuplicateLetters(string s) {
        vector<int> count(26);
        for (auto c : s) {
            count[c - 'a']++;
        }
        
        string res;
        vector<bool> inRes(26);
        for (int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']--; //how many s[i] left
            //for same char at different positions, the earlier the better (greedy)
            if (inRes[s[i] - 'a']) {
                continue;
            }
            //for different char at same position, the smaller the better (greedy)
            //precondition is the replaced char would appear later
            while (! res.empty() && s[i] <= res.back() && ! inRes[s[i] - 'a'] && count[res.back() - 'a'] > 0) {
                inRes[res.back() - 'a'] = false;
                res.pop_back();
            }
            res.push_back(s[i]);
            inRes[s[i] - 'a'] = true;;
        }
        return res;
    }