C++ simple solution easy understanding


  • 69
    L
    string removeDuplicateLetters(string s) {
        vector<int> cand(256, 0);
        vector<bool> visited(256, false);
        for (char c : s)
            cand[c]++;
        string result = "0";
        for (char c : s) {
            cand[c]--;
            if (visited[c]) continue;
            while (c < result.back() && cand[result.back()]) {
                visited[result.back()] = false;
                result.pop_back();
            }
            result += c;
            visited[c] = true;
        }
        return result.substr(1);
    }

  • 0
    D
    This post is deleted!

  • 0
    B

    Nice clever solution :-).

    Just a nit. Is the initialization of result with "0" really needed ? Even an empty string has the null character. Hence the result.back() works even with a null string.


  • 0
    G

    It is necessary because the sting::back function shall not be called on empty strings.


  • 19
    2

    I think this solution is really concise! But I want to add some detailed explainations to show why we do so to solve the problem, This problem is in fact similiar to the problem "Largest Rectangle under the histogram "

    We need to keep the monotically decreasing substring that contains all the char in the s. So we just use a vector to mimic the stack! Just similiar to the previous many solutions that use the vector to simulate a stack.

    In fact this problem is also similiar to the problem that the maximum in the sliding windows, I strongly recommend you to grasp the sliding windows solutions.

    Here is the AC C++ implementation

    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            vector<int> dict(256, 0);
            vector<bool> visited(256, false);
            for(auto ch : s)  dict[ch]++;
            string result = "0";
            /** the key idea is to keep a monotically increasing sequence **/
            for(auto c : s) {
                dict[c]--;
                /** to filter the previously visited elements **/
                if(visited[c])  continue;
                while(c < result.back() && dict[result.back()]) {
                    visited[result.back()] = false;
                    result.pop_back();
                }
                result += c;
                visited[c] = true;
            }
            return result.substr(1);
        }
    };
    

  • 0
    F

    such clever of the result.back;


  • 0
    X

    @2333333 I think you mean monotonically increasing substring. not monotically decreasing substring.


  • 0

    nice thought, simple solution


  • 2
    D

    adding a '0' before result just to handle the empty case seems not worth it, I think the following code would be easier to understand.

    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            unordered_map<char, bool> visited;
            unordered_map<char, int> counter;
            string result = "";
            for (auto c : s) counter[c]++;
            for (auto c : s) {
                counter[c]--;
                if (visited[c]) continue;  
                while (!result.empty() && c < result.back() && counter[result.back()] > 0) {
                    visited[result.back()] = false;
                    result.pop_back();
                }
                result += c;
                visited[c] = true;
            }
            return result;
        }
    };
    

  • 0
    E

    can you explain what's the time complexity of this solution , i guess O(n) ? since in the while loop, it's O(26) so it's O(n) * O(26) -> O(N)?


Log in to reply
 

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