O(n) c++ solution


  • 9
    D
    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            int counts[26] = {};
            bool inresult[26] = {};
            for(char c: s) counts[c-'a']++;
            string result = "";
            for(char c: s) {
                counts[c-'a']--;
                if(inresult[c-'a']) continue;
                while(!result.empty() && counts[result.back()-'a']>0 && result.back()>c){
                    inresult[result.back()-'a'] = false;
                    result.pop_back();
                }
                inresult[c-'a'] =true;
                result.push_back(c);
            }
            return result;
        }
    };

  • 1
    L

    It takes me some time to figure it out.

    In case if anyone needs explanation, I would write down my understanding of this code.

    Basically, it works like following:

    For each c in string
        while (c still has duplicates) and (c < result.back())
            result.pop_back()
        result.push_back(c)
    return result
    

    The invariant of this algorithm is that current result has no duplicate letter, always with the smallest lexicographical order so far.


  • 0
    T

    Thank you for your explanation! It really helpful!


Log in to reply
 

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