316. Remove Duplicate Letters

Given a string s, 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.

• Time : O(n)
• Space : O(1)

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int arr[26]{0,};
        int contain = 0;
        for(auto& ch : s) ++arr[ch-'a'];
        string res;
        for(auto& ch : s) {
            while(!res.empty() && res.back() > ch && arr[res.back() - 'a'] && !(contain & (1<<(ch-'a')))) {
                contain ^= (1<<(res.back()-'a'));
                res.pop_back();
            }
            --arr[ch-'a'];
            if(!(contain & (1<<(ch-'a')))) {
                res += ch;
                contain |= (1<<(ch-'a'));
            }
        }
        return res;
    }
};