Short 16ms O(n) c++ solution using stack which can be optimized down to 4ms


  • 24
    H
    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            unordered_map<char, int> cnts;
            string ret;
            stack<char> stk;
            vector<bool> isVisited(26, false);
            for (char each : s) cnts[each] ++;
            for (int i = 0; i < s.size(); cnts[s[i]] --, ++ i) {
                if (isVisited[s[i] - 'a'] || (!stk.empty() && stk.top() == s[i])) continue;
                while (!stk.empty() && stk.top() > s[i] && cnts[stk.top()] > 0) {
                    isVisited[stk.top() - 'a'] = false;
                    stk.pop();
                }
                stk.push(s[i]);
                isVisited[s[i] - 'a'] = true;
            }
            while (!stk.empty()) {
                ret.push_back(stk.top());
                stk.pop();
            }
            reverse(ret.begin(), ret.end());
            return ret;
        }
    };

  • 0
    H

    any question?


  • 0
    J

    It seems to be the true O(n) (not O(26n)) algorithm, can you explain the idea further?


  • 0
    H
    This post is deleted!

  • 1
    H

    Here is the explaination.

    the core idea is to keep the stack.
    and the stack is used to keep the current minimal char. if the next char is less than the top of stack ,then the top should be poped unless the top can not be poped.
    when can't we pop the top of stack ? the char is the last time to be seen in the raw string, then we can't pop it.(that's the power of cnts which can be implemented in vector~ less time maybe.)

    that’s all.
    Have I made myself understood ?


  • 0
    H

    Here is the explaination.

    the core idea is to keep the stack.
    and the stack is used to keep the current minimal char. if the next char is less than the top of stack ,then the top should be poped unless the top can not be poped.

    when can't we pop the top of stack ? the char is the last time to be seen in the raw string, then we can't pop it.(that's the power of cnts which can be implemented in vector~ less time maybe.)

    that’s all.
    Have I made myself understood ?


  • 0
    J

    Thank for your explanation, but I still have one problem
    if (isVisited[s[i] - 'a']...)
    I cannot understand why we should ignore the current character if it's already in the stack?

    BTW, I tried to optimize your code without modifying the logic, and it can be improved to 4ms.


  • 0
    H
     Wow! nice work~4ms...
     about the question,for example:
     input: dfad
     return:dfa
     without ignoring the current character already in the stack the answer will be dfad

  • 3

    That is really a smart usage of stack!

    Using your idea of stack, I rewrite it without explicitly using the class stack. I directly store the characters in the final result.

    Edited
    According to StefanPochmann and others' suggestions, I deleted the unneccessary || (!results.empty() && (results.back() == c)).

    4ms code:

    class Solution {
    public:
    	string removeDuplicateLetters(string s) {
    		vector<int> cnts(256, 0);
    		for (char c : s) {
    			++cnts[c];
    		}
    		
    		vector<bool> isVisited(256, false);		
    		string results;
    		for (char c : s) {
    			--cnts[c];
    			
    			if (isVisited[c]) { // this char appearred earlier
    				continue;
    			}
    			while (!results.empty() && (results.back() > c) 
                                && (cnts[results.back()] > 0)) { // a better option found
    				// rewithdraw the previous decision
    				isVisited[results.back()] = false;
    				results.pop_back();
    			}
    			// set up this new record
    			results.push_back(c);
    			isVisited[c] = true;
    		}
    
    		return results;
    	}
    };

  • 0
    H
    This post is deleted!

  • 0

    @halibut already changed accordingly. Thanks for your comment.


  • 28

    Your idea, just a bit shorter.

    Similar to but slightly shorter than zhiqing_xiao's, which I didn't see before. Main differences are my sentinel (the space char), that I don't have the unnecessary results.back() == c check, and the imho better variable names.

    Takes 4 ms as well.

    string removeDuplicateLetters(string s) {
        int ahead[256] = {};
        for (char c : s)
            ahead[c]++;
    
        string result = " ";
        bool inresult[256] = {};
    
        for (char c : s) {
            ahead[c]--;
            if (inresult[c])
                continue;
            while (c < result.back() && ahead[result.back()]) {
                inresult[result.back()] = false;
                result.pop_back();
            }
            result += c;
            inresult[c] = true;
        }
    
        return result.substr(1);
    }
    

  • 0
    Z

    More concise and understandable!


  • 0
    R

    Thanks, but no your explanation is not very clear to me. What do you mean by current minimal character? Why exactly do you need the stack. What's the logic?


  • 0
    P

    nice!
    more understandable!


  • 0
    J

    Good code!
    I have one comment. I think we do not need this line:
    || (!results.empty() && (results.back() == c))

    which is a case that is impossible to happen


  • 0
    L

    It seems without || (!results.empty() && (results.back() == c)) this code can still pass the OJ


  • 0
    C

    why initialize the result as a string contain the empty space, then discard the empty space use the substr() method?


  • 0

    @cyqiii Like I said, that's a sentinel. It allows me to simply access result.back() without having to always check whether result is non-empty.


  • 0
    V

    Is this O(n)? Or can it degrade to n^2 in case the input string is like "bcdeadcbe"? Looks like it can.


Log in to reply
 

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