Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复，实际在问如何从多个字符选取一个保留，从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a'，就要选靠前位置的保留，而低顺位字符如’z'则应该尽量选取靠后位置保留。

算法大概思路：每看到一个字符，我们要决定是否保留

1. 如果改字符已经被保留过，那么就跳过无需处理

2. 如果没有被保留，而且该字符是高顺位字符，那么我们要看能不能删掉前面已经保留的字符从而让该字符更靠前

2a. 如果前面的字符顺位更高，那就停止删除

2b. 前面字符顺位更低，但能否删除前面字符取决于之后是不是还会看到该字符；因此我们事先要建一个表，存储每个字符最晚出现的位置，如果当前位置小于最晚出现位置，那么我们可以删除之

3. 重复2a-2b直到停止，加入新字符

class Solution {

public:

    string removeDuplicateLetters(string s) {

        vector<char> stack;

        unordered_map<char,int> lastSeen;

        unordered_set<char> seen;

        for(int i=0; i<s.size(); i++){

            lastSeen[s[i]]=i;

        }

        for(int i=0; i<s.size(); i++){

            if(seen.count(s[i])==0) {

                while(stack.size()>0 && canRemove(lastSeen, stack.back(), s[i], i)){

                    seen.erase(stack.back());

                    stack.pop_back();

                }

                stack.push_back(s[i]);

                seen.insert(s[i]);

            }  

        }

        string res="";

        for(char c: stack){

            res+=c;

        }

        return res;

    }

    bool canRemove(unordered_map<char,int> lastSeen, char c, char cur, int i){

        if(c < cur){

            return false;

        }

        if(lastSeen[c]<=i){

            return false;

        }

        return true;

    }

};