316.Remove Duplicate Letters

Tags: Greedy Hard String

Links: https://leetcode.com/problems/remove-duplicate-letters/

---

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

---

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res  = "0";
        map<char, int> m;
        vector<bool> visit(26, false);

        for (int i = 0; i < s.size(); ++i) ++m[s[i]];
        for (char e : s) {
            --m[e]; //此时m记录的是剩余的e的数量
            if (visit[e - 'a']) continue; //当前字母已经使用过了
            while (e < res.back() && m[res.back()]) {
                visit[res.back() - 'a'] = false;
                res.pop_back();
            }
            res.push_back(e);
            visit[e - 'a'] = true;
        }

        return res.substr(1);
    }
};

本质的思想是单调栈，只不过这里用数组来模拟。初始res为"0"是为了保证第一个数字一定会被加进去。

这道题的思路是，考虑从头遍历字符串，为了让字典序最小，那么肯定是字母越小的排在越靠前最好，但是会有例外，比如对于字符串"dabb"，因为只有一个字母d，是不能去改变其顺序的，所以修改顺序需要满足两个条件，结果res的最后一个字符大于当前字符并且这个字符不是最后一个字符。