string removeDuplicateLetters(string s) {
vector<int> cand(256, 0);
vector<bool> visited(256, false);
for (char c : s)
cand[c]++;
string result = "0";
for (char c : s) {
cand[c];
if (visited[c]) continue;
while (c < result.back() && cand[result.back()]) {
visited[result.back()] = false;
result.pop_back();
}
result += c;
visited[c] = true;
}
return result.substr(1);
}
C++ simple solution easy understanding


I think this solution is really concise! But I want to add some detailed explainations to show why we do so to solve the problem, This problem is in fact similiar to the problem "Largest Rectangle under the histogram "
We need to keep the monotically decreasing substring that contains all the char in the s. So we just use a vector to mimic the stack! Just similiar to the previous many solutions that use the vector to simulate a stack.
In fact this problem is also similiar to the problem that the maximum in the sliding windows, I strongly recommend you to grasp the sliding windows solutions.
Here is the AC C++ implementation
class Solution { public: string removeDuplicateLetters(string s) { vector<int> dict(256, 0); vector<bool> visited(256, false); for(auto ch : s) dict[ch]++; string result = "0"; /** the key idea is to keep a monotically increasing sequence **/ for(auto c : s) { dict[c]; /** to filter the previously visited elements **/ if(visited[c]) continue; while(c < result.back() && dict[result.back()]) { visited[result.back()] = false; result.pop_back(); } result += c; visited[c] = true; } return result.substr(1); } };

@2333333 I think you mean
monotonically increasing substring
. notmonotically decreasing substring
.

adding a '0' before result just to handle the empty case seems not worth it, I think the following code would be easier to understand.
class Solution { public: string removeDuplicateLetters(string s) { unordered_map<char, bool> visited; unordered_map<char, int> counter; string result = ""; for (auto c : s) counter[c]++; for (auto c : s) { counter[c]; if (visited[c]) continue; while (!result.empty() && c < result.back() && counter[result.back()] > 0) { visited[result.back()] = false; result.pop_back(); } result += c; visited[c] = true; } return result; } };