316 Remove Duplicate Letters

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

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Solution

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int n = s.size();
        vector<int> count(26, 0);
        vector<bool> added(26, false);
        for ( int i = 0; i < n; i++ ) count[s[i]-'a'] += 1;
        string res;
        for ( int i = 0; i < n; i++ ) {
            count[s[i]-'a'] -= 1;
            if ( added[s[i]-'a'] ) continue;
            while ( res != "" ) {
                char last = res[res.size()-1];
                if ( s[i] > last or count[last-'a'] == 0 ) break;
                added[last-'a'] = false;
                res = res.substr(0, int(res.size())-1);
            }
            res += s[i];
            added[s[i]-'a'] = true;
        }
        return res;
    }
};

Notes
用一个数组count记录每个字母出现的次数。
然后重新遍历字符串，并且额外用一个bool数组added记录字母是否已经加入最终的字符串。 当遍历到s[i]的时，

• count[s[i]-'a'] -= 1;
• 如果它已经加入字符串，则继续遍历；
• 往前看当前的res字符串，如果最后一个字符last的count不为零 count[last-''a] != 0，并且last > s[i]，那么这个时候我们可以用s[i]代替last.