Leetcode316- remove duplicate letters - stack - greedy - string

Original link

Note：

Maintain an answer string , Traverse the given string , Judge the current character each time , Is it smaller than the end of the answer string , If it's small , Let's see if the last one can be deleted , Delete if you can , You can't delete it. There's no way , Just keep it

The code is as follows ：

class Solution {
    
public:
    string removeDuplicateLetters(string s) {
    
        string stk;
        unordered_map<char, bool> ins;
        unordered_map<char, int> last;
        for(int i = 0; i < s.size(); i ++)  last[s[i]] = i;

        for(int i = 0; i < s.size(); i ++){
    
            if(ins[s[i]])   continue;
            while(stk.size() && stk.back() > s[i] && last[stk.back()] > i){
    
                ins[stk.back()] = false;
                stk.pop_back();
            }

            ins[s[i]] = true;
            stk += s[i];
        }

        return stk;
    }
};