# Clear C++ O(n) iterative code borrowed idea from lixx2100's greedy solution with detailed explanation

• The greedy idea is simple here. There are basically two cases here but I will use three cases in this post to help you understand these scenarios.

``````1. When the smallest letter is on the left-most position, `newString = s[0] + s.substr(1).replace(s[0], '')`
2. When smallest letter is not on the left-most position:
(1): If letters on its left have duplications on its right, e.g.: bc[a]cb, drop all of them. `newString = s[i] + substr(i).replace(s[i], '')`
(2): Else, use local smallest as s[i]
``````

You can easily figure out that case 1 and 2(1) are just the same. The code is shown below.

``````class Solution {
public:
string removeDuplicateLetters(string s) {
string result = "";
while (!s.empty()) {
int count[26] = {0};
int smallest = 0;
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (c < s[smallest]) {
smallest = i;
}
count[c - 'a']++;
}

int localSmallest = 0;
for (int i = 0; i < smallest; i++) {
char c = s[i];
if (c < s[localSmallest]) {
localSmallest = i;
}
count[c - 'a']--;
if (count[c - 'a'] == 0) {
smallest = localSmallest;
break;
}
}

result += s[smallest];

// Replace all of successive s[smallest] with ''
string newStr;
newStr.reserve(s.size() - smallest - 1);
for (int i = smallest + 1; i < s.size(); i++) {
if (s[i] != s[smallest]) {
newStr += s[i];
}
}

s = newStr;
}

return result;
}
};
``````

Since there are only 26 letters in English alphabet, the complexity is O(26*n) = O(n).

Hopefully this post is not too long and can help you understand the algorithm. I personally feel hard to understand those one liner stuffs so I rewrite it in a more understandable fashion.

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