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;
}