# Leetcode Remove Duplicate Letters problem solution

In this Leetcode Remove Duplicate Letters problem solution You are given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

## Problem solution in Python.

```class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
stack = []
cnt = collections.Counter(s)
for ch in s:
if ch not in stack:
while stack and ch <= stack[-1] and cnt[stack[-1]] > 1:
cnt[stack.pop()] -=1
stack.append(ch)
else:
cnt[ch] -=1
return "".join(stack)
```

## Problem solution in Java.

```StringBuilder sb = new StringBuilder();
int[] count = new int[26];

public String removeDuplicateLetters(String s) {

char[] schar = s.toCharArray();
for(char c : schar){
count[c - 'a']++;
}
helper(schar, 0);
return sb.toString();
}

private void helper(char[] schar, int start){

if(start == schar.length) return;
int pos = -1, i = start;
char cpos = 255;
for(;i < schar.length; i++) {
if(count[schar[i] - 'a'] == -1) continue;
if (schar[i] < cpos){
pos = i;
cpos = schar[i];
}
if (--count[schar[i] - 'a'] == 0){
i++;
break;
}
}

if(pos == -1) return;
sb.append(cpos);
count[cpos - 'a'] = -1;
for(int n = pos + 1; n < i; n++){
if(count[schar[n] - 'a'] != -1) count[schar[n] - 'a']++;
}
helper(schar, pos + 1);
}
```

## Problem solution in C++.

```string removeDuplicateLetters(string s){

vector<bool> exist(26,false);
vector<int> freq(26,0);
stack<char> st;
string res;
if(s.length()==1)   return s;

for(auto ch: s){
freq[ch-'a']++;
}

for(int i=0; i<s.length(); i++){
char ch= s[i];

freq[ch-'a']--;
if(exist[ch-'a']){
continue;
}

while(st.size()>0 && st.top()>ch && freq[st.top()-'a']>0 ){
char top= st.top();
st.pop();
exist[top-'a']= false;
}
st.push(ch);
exist[ch-'a']= true;
}
while(st.size()>0){
res.push_back(st.top());
st.pop();
}
reverse(res.begin(),res.end());

return res;
}
};
```

## Problem solution in C.

```char* removeDuplicateLetters(char* s)
{
int len = strlen(s);
if (len < 2)
return s;
int count[26] = { 0 }, choosen[26] = { 0 }, rlen = 0;
for (int i = 0; i < len; i++) {
count[s[i] - 'a']++;
if (count[s[i] - 'a'] == 1)
rlen++;
}
char* result = (char*)malloc(sizeof(char) * (rlen + 1));
for (int i = 0, j = 0; i < len; i++) {
count[s[i] - 'a']--;
if (choosen[s[i] - 'a'])
continue;
while (j > 0 && s[i] < result[j - 1] && count[result[j - 1] - 'a'] > 0) {
choosen[result[j - 1] - 'a'] = 0;
j--;
}
result[j++] = s[i];
choosen[s[i] - 'a'] = 1;
}
result[rlen] = '\0';
return result;
}
```