# scoyer_result(C++)

• Firstly, We find the first position of the 'last' character, for example, the first position of “aabac” is 2 (index starts from 0), “ababv” ' s result is 2 too.

Secondly, we find the minimum letter c from the beginning to the position we find in the first step, and mark the position as min_pos.

Thirdly, we delete the c from the min_pos + 1 to the end, add the result c, the remaining string is ns.

Lastly, pass the new string ns for doing the step1~3 recursively.

Why does the algorithm works?
The reason why we find the 'last position' in the first step is that you must choose a letter from the beginning to the 'last position'. In greedy algorithm, we have better choose the optimal letter during this segment. So the algorithm works.

My Code:

``````class Solution {
public:
string removeDuplicateLetters(string s) {
if (s.empty()) {
return s;
}
vector<int> cnt(26, 0);
int n = s.length();
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']++;
}
int min_pos = 0;
for (int i = 0; i < n; i++) {
if (s[min_pos] > s[i]) min_pos = i;
if (!--cnt[s[i] - 'a']) break;
}
string ns;
for (int i = min_pos + 1; i < n; i++) {
if (s[i] == s[min_pos]) continue;
ns.push_back(s[i]);
}
string ret;
ret.push_back(s[min_pos]);
return ret + removeDuplicateLetters(ns);
}
};
``````

• Thanks for sharing this alternate greedy method.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.