# 316. 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"

# Solution

Approach 1: Stack.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> count(26, 0);
        for (int i = 0; i < s.size(); ++i)
        {
            count[s[i]-'a']++;
        }
        string res = s;
        int tail = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int letter = s[i] - 'a';
            if (count[letter] == 0)
            {
                continue;
            }
            else if (count[letter] > 0)
            {
                // The unique letter or
                // the first appearence of the duplicated letter.
                while (tail > 0 && count[res[tail-1]-'a'] != 0 && res[tail-1] >= s[i])
                {
                    // Only duplicated letters can be removed.
                    count[res[tail-1]-'a'] = 0 - count[res[tail-1]-'a'];
                    tail--;
                }
                res[tail] = s[i];
                tail++;
                count[letter]--;
                // Mark the duplicated letter by reversing its count.
                if (count[letter] > 0)
                    count[letter] = 0 - count[letter];
            }
            else if (count[letter] < 0)
            {
                // This duplicated letter is already recorded before.
                count[letter]++;
            }
        }
        return res.substr(0, tail);
    }
};