316. Remove Duplicate Letters

The important point for this problem is that the result must keep the order of input string and also must be the smallest in lexicographical order among all possible results. To achieve this goal, the idea is to keep the smallest lexicographical order string so far. Whenever we meet a new letter that is smaller than the last letter in the result string, we check if the letter will appear later. If so, we can pop out the letter. We should keep popping out letters until there's no more letter later or the new letter becomes lager. And then we push the new letter to the back of result.

1:  class Solution {  
2:  public:  
3:    string removeDuplicateLetters(string s) {  
4:      vector<int> count(26, 0);  
5:      vector<bool> visited(26, false); // "cbacdcbc" 
6:      string res;  
7:      for (char c : s) {  
8:        count[c-'a']++;  
9:      }  
10:      for (char c : s) {  
11:        count[c-'a']--;  
12:        if (visited[c-'a']) continue;  
13:        while (!res.empty() && res.back() > c && count[res.back()-'a'] > 0) {  
14:          visited[res.back()-'a'] = false;  
15:          res.pop_back();  
16:        }  
17:        res += c;  
18:        visited[c-'a'] = true;  
19:      }  
20:      return res;  
21:    }  
22:  };