C++ 4ms (fastest so far) with detail comments


  • 1
    W
        string removeDuplicateLetters(string s) {
                // remove consecutive letters: "aaabbbccc" -> "abc"
                string t;
                for (int i=0; i<s.length(); i++)
                    if (i==0 || s[i]!=s[i-1])
                        t += s[i];
                s=t;
                
                // declare stk: stack, freq: char frequency in s, inStk: if a char already in stack
                vector<char> stk;
                vector<int> freq(256, 0), inStk(256, 0);
                
                // get frequency
                for (char c : s)
                    freq[c]++;
                
                for (char c : s) {
                    if (inStk[c]) // if already in stack, discard this char
                        freq[c]--;
                    else {
                        if (!stk.empty() && c<stk.back())
                            while (stk.size()>0 && c<stk.back() && freq[stk.back()]>1) 
    // when stack.top>char and there are more such top behind, this top can be removed to obey lexi order
                            {
                                freq[stk.back()]--, inStk[stk.back()]=0;
                                stk.pop_back();
                            }
                        stk.push_back(c);
                        inStk[c]=1;
                    }
                }
                return string(stk.begin(), stk.end());
            }

Log in to reply
 

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