# A short O(n) recursive greedy solution

• Given the string s, the greedy choice (i.e., the leftmost letter in the answer) is the smallest s[i], s.t.
the suffix s[i .. ] contains all the unique letters. (Note that, when there are more than one smallest s[i]'s, we choose the leftmost one. Why? Simply consider the example: "abcacb".)

After determining the greedy choice s[i], we get a new string s' from s by

1. removing all letters to the left of s[i],
2. removing all s[i]'s from s.

We then recursively solve the problem w.r.t. s'.

The runtime is O(26 * n) = O(n).

``````public class Solution {
public String removeDuplicateLetters(String s) {
int[] cnt = new int[26];
int pos = 0; // the position for the smallest s[i]
for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) < s.charAt(pos)) pos = i;
if (--cnt[s.charAt(i) - 'a'] == 0) break;
}
return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
}
}``````

• ``````        /**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function(s) {
var arr = s.split("");
arr.sort();
var tmpstr = "";
var result = [];
for(var i = 0; i < arr.length; i++){
if(arr[i]!==tmpstr){
result.push(arr[i]);
tmpstr = arr[i];
}else{
continue;
}
}
return result.join("");
};``````

• The runtime looks like O(n^2) to me :)
As every time when removeDuplicateLetters is called, it goes through the whole string to collect cnt, and s.substring(j + 1).replaceAll("" + ch, "") is O(n) as well because it runs through the whole string.

• Each recursive call takes O(n), but at most 26 recursive calls will be triggered.

• That makes sense, the final result is no longer than 26 :) Nice solution!

• I really like your solution, this is my Python version of it.

``````def removeDuplicateLetters(s):
idx = lambda c: ord(c) - ord('a')
cnt = [0] * 26
for c in s:
cnt[idx(c)] += 1

candidate = [0] * 26
for c in s:
i = idx(c)
if cnt[i] >= 1:
candidate[i] = 1
cnt[i] -= 1
if cnt[i] == 0:
break

for i in xrange(0, 26):
if candidate[i]:
ch = chr(ord('a') + i)
return ch + removeDuplicateLetters(s[s.find(ch):].replace(ch, ""))
return ""``````

• I am glad you like it. :)

I just optimized my code, and it looks even shorter now.

• This idea is really smart. Come up with a Ten lines python code:

``````def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
if not s: return ""
counts = collections.Counter(list(s))

pos = 0
for i, x in enumerate(s):
if x < s[pos]: pos = i
counts[x] -= 1
if counts[x] == 0: break

return s[pos] + self.removeDuplicateLetters(s[pos+1:].replace(s[pos], ""))``````

• That's even nicer, it's a shame that I couldn't vote twice :p

• Iterative Version, use '}' to mark elements that we deleted.

``````string removeDuplicateLetters(string s) {
string res;
int p=0;
while(p<s.size()){
vector<int> cnt(256,0);
for(int i=p; i<s.size(); i++) if(s[i]!='}') cnt[s[i]]++;
int nxtp=p;
for(int i=p; i<s.size(); i++){
if(s[i]<s[nxtp]) nxtp=i;
if(--cnt[s[i]]==0) break; //unique in suffix s[i...]
}
for(int j=p; j<s.size(); j++){
if(j<nxtp || s[j]==s[nxtp] && j>nxtp) s[j]='}';
}
while(p<=nxtp || s[p]=='}') p++;
}
for(auto c: s) if(c!='}') res.push_back(c);
return res;
}``````

• Like your python solution! Especially the lambda way.

• Very elegant!
I have a similar C++ iterative solution using bit manipulation

``````class Solution {
public:
string removeDuplicateLetters(string s) {

int next = 0;
for (int i = s.length() - 1; i >= 0; --i) {
int b = (1 << (s[i] - 'a'));
if (!(next & b)) {
}
else
}

int cnt = setBits(next);
int ind = 0;
int used = 0;
string ret = "";
for (; cnt; --cnt) {
while (used & (1 << (s[ind] - 'a')))
++ind;

int best = ind++;

for (; ind < s.length() && val == (masks[ind] & ~(masks[ind] & used)); ++ind) {
int b = 1 << (s[ind] - 'a');
if (used & b)
continue;

if (s[ind] < s[best])
best = ind;
}

ret += s[best];
ind = best + 1;
used |= (1 << (s[best] - 'a'));
}

return ret;
}

private:
int setBits(int n) {
int cnt = 0;
for (int i = 0; i < 26; ++i)
if (n & (1 << i))
++cnt;
return cnt;
}
};``````

• yes, u are right

• cnt was created using "new" and it is not released. Memory leak!

• @xuezhou, in Java, one does not need to release the allocated memory explicitly, and the garbage collection is normally handled by JVM.

In C/C++ instead, an easy way is to replace `int[] cnt = new int[26];` by `int cnt[26] = {0};` so that the memory will be allocated on the stack, and thus will automatically be released when the function is finished.

• yes, you are right.

• Recursive looks much cleaner than iterative solution.

• This post is deleted!

• just one question: how to understand the line；if (--cnt[s.charAt(i) - 'a'] == 0) break;　ｗｈｙ　ｙｏｕ　ｃｈｏｏｓｅ　ｔｏ　ｂｒｅａｋ　ｔｈｅ　ｌｏｏｐ　ｗｈｅｎ --count[s.charAt(i) - 'a' ] ==0 ?

• The suffix `s[i+1 ..]` will no longer contain character `s[i]`, hence no need to proceed any further.

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