Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

一刷
题解：
让我们移除重复字母，使得每个字符只能出现一次，而且结果要按字母顺序排，前提是不能打乱其原本的相对位置。

public class Solution {
    public String removeDuplicateLetters(String s) {
        if(s == null || s.length() == 0) return s;
        int[] count = new int[26];
        char[] res = new char[26];
        int len = s.length();
        for(int i=0; i<len; i++){
            count[s.charAt(i) - 'a']++;
        }
        int pos = 0;
        for(int i=0; i<len; i++){
            if(s.charAt(i) < s.charAt(pos)) 
                pos = i;
            count[s.charAt(i) - 'a']--;
            if(count[s.charAt(i) - 'a'] == 0)
                break; // found first minimum char
        }
        
        String charToRemove = String.valueOf(s.charAt(pos));
        return charToRemove + removeDuplicateLetters(s.substring(pos+1).replaceAll(charToRemove, ""));
    }
}

二刷
用26维数组存储词频，用26维boolean数组表示该character是否存在当前的stack中。对于一个ch, 如果栈顶的元素都比ch大，且栈顶元素的词频此时不为0（有dup），则一直pop. 最后用linkedlist模拟stack, 进一步提高速度，stack中的顺序即为remove dup后的字符串（从早到晚）

public class Solution {

   public static String removeDuplicateLetters(String sr) {
        int[] res = new int[26]; //will contain number of occurences of character (i+'a')
        boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack
        char[] ch = sr.toCharArray();
        for(char c: ch){  //count number of occurences of character 
            res[c-'a']++;
        }
        Deque<Character> st = new LinkedList<>(); // answer stack
        int index;
        for(char s:ch){ 
            index= s-'a';
            res[index]--;   //decrement number of characters remaining in the string to be analysed
            if(visited[index]) //if character is already present in stack, dont bother
                continue;
            //if current character is smaller than last character in stack which occurs later in the string again
            //it can be removed and  added later e.g stack = bc remaining string abc then a can pop b and then c
            
            while(!st.isEmpty() && s<st.peekLast() && res[st.peekLast()-'a']!=0){ 
                visited[st.removeLast()-'a']=false;
            }
            st.addLast(s); //add current character and mark it as visited
            visited[index]=true;
        }

        StringBuilder sb = new StringBuilder();
        //pop character from stack and build answer string from back
        while(!st.isEmpty()){
            sb.append(st.pop());//from first to last
        }
        return sb.toString();
   }
}

三刷

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] freq = new int[26];
        char[] strs = s.toCharArray();
        for(char ch : strs){
            freq[ch - 'a']++;
        }
        
        boolean[] visited = new boolean[26];
        LinkedList<Character> stack = new LinkedList<>();
        for(char ch : strs){
            int index = ch - 'a';
            freq[index]--;
            if(visited[index]) continue;//is in the stack
            while(!stack.isEmpty() && ch<stack.peekLast() && freq[stack.peekLast() - 'a']!=0){
                visited[stack.pollLast() - 'a'] = false;
            }
            stack.addLast(ch);
            visited[index] = true;
        }
        
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()){
            res.append(stack.pollFirst());
        }
        return res.toString();
    }
}