LeetCode-316 Remove Duplicate Letters

Description

给定一个字符串\(s\)，移除相同的字符使得每个字符只保留一份，且要求输出最小字典序

Constraints

\(s\)的长度不超过\(10^4\)

Solution

我讨厌字典序，用单调栈糊弄过去吧。意思很简单，就是看后面还有大字典序的话就pop()

Code

class Solution {
public:
    string removeDuplicateLetters(string s) {
        stack<char> stk;
        int cnt[256] {};
        bool in[256] {};
        for(auto c : s) cnt[c]++;
        for(auto c : s) {
            // count of right-hand side
            cnt[c]--;
            while(!stk.empty() && stk.top() > c && cnt[stk.top()] && !in[c]) {
                in[stk.top()] = false;
                stk.pop();
            }
            if(!in[c]) {
                in[c] = true;
                stk.push(c);
            }
        }
        for(s.clear(); !stk.empty();) s+=stk.top(), stk.pop();
        return {s.rbegin(), s.rend()};
    }
};

Link

LeetCode-316 Remove Duplicate Letters