A clean and understandable C++ solution 20 ms.


  • 0
    G
    class Solution {
    public:
        string removeDuplicateLetters(string s) 
        {
            string Res;
            unordered_map<char,int> LookFor;
            unordered_map<char,int> Found;
            
            if(s.empty())
            {
                return s;
            }
            
            for(const auto c: s)
            {
                if(LookFor.find(c) == LookFor.end())
                {
                    LookFor[c] = 1;
                }
                else
                {
                    LookFor[c]++;
                }
            }
            
            Res.push_back(s[0]);
            LookFor[s[0]]--;
            Found.insert(make_pair(s[0],1));
            
            for(int i = 1; i < s.size(); ++i)
            {
                if(s[i] > Res.back() && Found.find(s[i]) == Found.end())
                {
                    Res.push_back(s[i]);
                    LookFor[s[i]]--;
                    Found.insert(make_pair(s[i],1));
                }
                else if(s[i] < Res.back())
                {
                    while(Res.empty() == false && s[i] < Res.back() && LookFor[Res.back()] > 0 && Found.find(s[i]) == Found.end())
                    {
                        Found.erase(Res.back());
                        Res.pop_back();
                    }
                    
                    LookFor[s[i]]--;
                    
                    if(Found.find(s[i]) == Found.end())
                    {
                        Res.push_back(s[i]);
                        Found.insert(make_pair(s[i],1));
                    }
                }
                else if(s[i] == Res.back())
                {
                    LookFor[s[i]]--;
                }
            }
            
            return (Res);
        }
    };

Log in to reply
 

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