My simple C++ O(N) solution, 4ms


  • 5
    D

    The key is to get an auxiliary array to save the index of the last occurence of each letter in S. Then we do greedy algorithm: scan the string from left to right, for the current letter s[i], if it is already included then move on, if not, check if the previously included letter in res (from back to begin) if larger than s[i], if yes and such res.back() letter has occurence after the current position i, then drop it from res and reset the included flag (since it can reduce res and res.back() can still be added back later on), and repeat to check the new res.back(). If s[i]> res.back() or res.back() has no occurence after i, then, just add s[i] to res.
    Two key arrays are used in the following code
    lastIdx[i]: the last occurence index of letter 'a'+i in s
    included[i]: if 'a'+i is already included in res

       class Solution {
        public:
            string removeDuplicateLetters(string s) {
                int sLen = s.size(), i, lastIdx[26]={0},resLen=0, included[26]={0};
                string res;
                for(i=sLen-1; i>=0 && resLen<26;--i) //generate lastIdx array
                       if(!lastIdx[s[i]-'a']) {
                        lastIdx[s[i]-'a'] = i; 
                        ++resLen;
                      }  
                for(i=0; i<sLen;++i) 
                { //scan s from left to right
                    if(!included[s[i]-'a'])
                    { // if s[i] is not included in s[i]
                        while(!res.empty() && s[i]<res.back() && lastIdx[res.back()-'a']>i)
                        { // pop res as much as possible to reduce res
                            included[res.back()-'a'] = 0;
                            res.pop_back();
                        }
                        included[s[i]-'a'] = 1; // add s[i] to res
                        res.push_back(s[i]);
                    }
                }
                return res;
            }
    };
    

    My first ugly version, 8ms, a little bit different auxilliary info used, less efficient and concise, 8ms

    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            if(s.size() <= 1) return s;
            string res;
            int sLen =s.size(), i, resL, inS[26]={0}, start=0, count[sLen+1] = {0};
            char curC = 'z'+1;
            for(i=sLen-1; i>=0; --i)
            {
                count[i] = count[i+1];
                if(inS[s[i]-'a']==0) 
                {
                    inS[s[i]-'a'] = 1;
                    ++count[i];
                }
            }
            resL = count[0];
            while(resL)
            {
                for(i=start, curC='z'+1;i==0 || count[i]==count[i-1] || inS[s[i-1]-'a']== 0;++i)
                    if(inS[s[i]-'a'] && s[i]<curC) {
                        curC=s[i]; 
                        start=i;
                    }
    
                inS[s[start]-'a']= 0;
                res.push_back(s[start++]);
                --resL;
            }
            return res;
        }
    };

  • 1
    L

    Nice solution. Generation of lastIndex array can be simplified as below -

        for (int i = 0; i < s.size(); ++i)
        {
            lastIndex[s[i] - 'a'] = i;
        } 

Log in to reply
 

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