# My simple C++ O(N) solution, 4ms

• The key is to get an auxiliary array to save the index of the last occurence of each letter in S. Then we do greedy algorithm: scan the string from left to right, for the current letter s[i], if it is already included then move on, if not, check if the previously included letter in res (from back to begin) if larger than s[i], if yes and such res.back() letter has occurence after the current position i, then drop it from res and reset the included flag (since it can reduce res and res.back() can still be added back later on), and repeat to check the new res.back(). If s[i]> res.back() or res.back() has no occurence after i, then, just add s[i] to res.
Two key arrays are used in the following code
lastIdx[i]: the last occurence index of letter 'a'+i in s
included[i]: if 'a'+i is already included in res

``````   class Solution {
public:
string removeDuplicateLetters(string s) {
int sLen = s.size(), i, lastIdx[26]={0},resLen=0, included[26]={0};
string res;
for(i=sLen-1; i>=0 && resLen<26;--i) //generate lastIdx array
if(!lastIdx[s[i]-'a']) {
lastIdx[s[i]-'a'] = i;
++resLen;
}
for(i=0; i<sLen;++i)
{ //scan s from left to right
if(!included[s[i]-'a'])
{ // if s[i] is not included in s[i]
while(!res.empty() && s[i]<res.back() && lastIdx[res.back()-'a']>i)
{ // pop res as much as possible to reduce res
included[res.back()-'a'] = 0;
res.pop_back();
}
included[s[i]-'a'] = 1; // add s[i] to res
res.push_back(s[i]);
}
}
return res;
}
};
``````

My first ugly version, 8ms, a little bit different auxilliary info used, less efficient and concise, 8ms

``````class Solution {
public:
string removeDuplicateLetters(string s) {
if(s.size() <= 1) return s;
string res;
int sLen =s.size(), i, resL, inS[26]={0}, start=0, count[sLen+1] = {0};
char curC = 'z'+1;
for(i=sLen-1; i>=0; --i)
{
count[i] = count[i+1];
if(inS[s[i]-'a']==0)
{
inS[s[i]-'a'] = 1;
++count[i];
}
}
resL = count[0];
while(resL)
{
for(i=start, curC='z'+1;i==0 || count[i]==count[i-1] || inS[s[i-1]-'a']== 0;++i)
if(inS[s[i]-'a'] && s[i]<curC) {
curC=s[i];
start=i;
}

inS[s[start]-'a']= 0;
res.push_back(s[start++]);
--resL;
}
return res;
}
};``````

• Nice solution. Generation of lastIndex array can be simplified as below -

``````    for (int i = 0; i < s.size(); ++i)
{
lastIndex[s[i] - 'a'] = i;
} ``````

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