4ms C++ solution, use return string as a stack


  • 22
    N
    string removeDuplicateLetters(string s) {
        vector<unsigned int> cnt(26,0); //only consider lowercase letters
        vector<bool> inRes(26, false); //true if the letter has been added to res 
        for(char ch:s) cnt[ ch-'a' ]++;
        string res = ""; //use res as a stack
        for(char ch:s){
           cnt[ ch-'a' ]--;
           if(res.empty()){ 
               res.push_back(ch);
               inRes[ ch-'a' ] = true;
               continue;
           }
           if(inRes[ch-'a']) continue;
           while(ch<res.back() && !res.empty() && cnt[ res.back()-'a' ]>0){
               inRes[ res.back()-'a' ] = false;
               res.pop_back();
               
           }
           res.push_back(ch);
           inRes[ ch-'a' ] = true;
        }
        return res;
    }

  • 0
    W

    Good solution!


  • 0

    I think this is more clear!


  • 0

    Thanks for sharing, this code is much easier to understand!


  • 0
    Q

    Great solution. Following code removes some redundant lines.

    string removeDuplicateLetters(string s) {
        vector<unsigned int> cnt(26,0); //only consider lowercase letters
        vector<bool> inRes(26, false); //true if the letter has been added to res 
        for(char ch:s) cnt[ ch-'a' ]++;
        string res = ""; //use res as a stack
        for(char ch:s){
           cnt[ ch-'a' ]--;
           if(inRes[ch-'a']) continue;
           while(!res.empty() && ch<res.back() && cnt[ res.back()-'a' ]>0){
               inRes[ res.back()-'a' ] = false;
               res.pop_back();
    
           }
           res.push_back(ch);
           inRes[ ch-'a' ] = true;
        }
        return res;
    }

Log in to reply
 

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