My 3ms greedy C++ solution.


  • 0
    M
    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            int first[256],next[s.length()],last[256];
            memset(first,0x7F,sizeof(first));
            memset(last,0x7F,sizeof(last));
            for(int i=s.length()-1;i>=0;--i){
                next[i]=first[s[i]];
                if(next[i]==0x7F7F7F7F) last[s[i]]=i;
                first[s[i]]=i;
            }
            string ans="";
            while(1){
                int minlast=0x7F7F7F7F;
                for(char c='a';c<='z';++c)
                    if(last[c]<minlast) minlast=last[c];
                if(minlast==0x7F7F7F7F)return ans;
                int pos=minlast;
                for(char c=s[pos];c>='a';--c)
                    if(first[c]<minlast) pos=first[c];
                ans+=s[pos];
                last[s[pos]]=first[s[pos]]=0x7F7F7F7F;
                for(char c='a';c<='z';++c)
                    while(first[c]<pos) first[c]=next[first[c]];
            }
        }
    };
    

Log in to reply
 

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