Simple and intuitive C++ with logic


  • 0
    V
    /* The logic here is delayed entry of larger characters: For example if there 
        is 'k' in ans and we want to insert 'g', if we know there is at least one 'k' 
        available in string s ahead, this 'g' will kick out 'k'(as 'g' < 'k') */
        string removeDuplicateLetters(string s) {
            string ans;
            set<char> present;
            vector<int> h(26, 0);
            for (auto c:s)
                h[c-'a']++;
            for (auto c : s) {
                if (present.find(c) == present.end()) { // this is new char
                    if (ans.length()) {
                        int i = ans.length() - 1;
                        while (i >= 0 && ans[i] > c && h[ans[i] - 'a']) { // ans[i] can be kicked out
                            present.erase(ans[i]);
                            i--;
                        }
                        if (i < (int)ans.length() - 1)
                            ans.erase(i+1);
                    }
                    ans += c;
                    present.insert(c);
                }
                h[c - 'a']--;
            }
            return ans;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.