forked from PRAN20/Top-Interview-Questions-LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Remove-Duplicate-Element.cpp
34 lines (31 loc) · 955 Bytes
/
Remove-Duplicate-Element.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
string removeDuplicateLetters(string s) {
int len = s.size();
string res = "";
unordered_map<char, int> M;
unordered_map<char, bool> V;
stack<int> S;
for (auto c : s) {
if (M.find(c) == M.end()) M[c] = 1;
else M[c]++;
}
for (unordered_map<char, int>::iterator iter=M.begin(); iter!=M.end(); iter++) V[iter->first] = false;
cout<<M.size()<<V.size()<<endl;
for (int i=0; i<len; i++) {
M[s[i]]--;
if (V[s[i]] == true) continue;
while (!S.empty() and s[i] < s[S.top()] and M[s[S.top()]] > 0) {
V[s[S.top()]] = false;
S.pop();
}
S.push(i);
V[s[i]] = true;
}
while (!S.empty()) {
res = s[S.top()] + res;
S.pop();
}
return res;
}
};