I have solved this problem years before, LeetCode: 316.Remove Duplicate Letters, but still stuck on it.

The key idea is not only about stack, but also required a map to record how many same letters behind current one. Which helps us to decide if drop current letter or not, when the new letter is less than the top of stack, which means smaller in lexicographical order.

class Solution {
public:
	string removeDuplicateLetters(string s) {
		vector<int> countOfLetters(26, 0);
		vector<bool> pickedLetters(26, false);
		stack<char> st;

		for (auto iter = s.begin(); iter != s.end(); ++iter) {
			countOfLetters[*iter - 'a']++;
		}

		for (int i = 0; i < s.size(); ++i) {
			countOfLetters[s[i] - 'a']--;
			if (pickedLetters[s[i] - 'a']) {
				continue;
			}
			while (!st.empty() && s[i] < st.top() && countOfLetters[st.top() - 'a'] > 0) {
				pickedLetters[st.top() - 'a'] = false;
				st.pop();
			}
			st.push(s[i]);
			pickedLetters[s[i] - 'a'] = true;

		}
		string r;
		while (!st.empty()) {
			r.push_back(st.top());
			st.pop();
		}
		reverse(r.begin(), r.end());
		return r;
	}
};