去除重复字母

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    string removeDuplicateLetters(string s) {
        const int MAXN = 26;
        vector<int> cnts(MAXN, 0);
        vector<bool> enter(MAXN, false);
        stack<char> stk;

        for (char ch : s) {
            cnts[ch - 'a']++;
        }

        for (char ch : s) {
            if (!enter[ch - 'a']) {
                while (!stk.empty() && stk.top() > ch && cnts[stk.top() - 'a'] > 0) {
                    enter[stk.top() - 'a'] = false;
                    stk.pop();
                }
                stk.push(ch);
                enter[ch - 'a'] = true;
            }
            cnts[ch - 'a']--;
        }

        string res = "";
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }

        reverse(res.begin(), res.end());
        return res;
    }
};