题目描述

去重，然后保证靠前的字母最小
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

样例

(贪心 Greedy) $O(26n)$

c++

string removeDuplicateLetters(string s) {
    vector<int> cand(256, 0);
    vector<bool> visited(256, false);
    for (char c : s)
        cand[c]++;
    string result = "0";
    /** the key idea is to keep a monotically increasing sequence **/
    for (char c : s) {
        cand[c]--;
        /** to filter the previously visited elements **/
        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);
}

Python3版

def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """

        cnt = collections.Counter(s)
        res, visited = [], set()

        for c in s:
            cnt[c] -= 1
            if c in visited:    continue

            while res and res[-1] > c and cnt[res[-1]] > 0:
                visited.remove(res[-1])
                res.pop()
            res.append(c)
            visited.add(c)

        return ''.join(res)