Problem_316. Remove Duplicate Letters - xwu36/LeetCode GitHub Wiki

Example:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

code:
My way:
class Solution {
    public String removeDuplicateLetters(String s) {
        int n = s.length();
        if(n == 0)
            return "";
        TreeMap<Character, List<Integer>> map = new TreeMap<>();
        for(int i = 0; i < n; i++){
            if(map.get(s.charAt(i)) == null)
                map.put(s.charAt(i), new ArrayList<>());
            map.get(s.charAt(i)).add(i);
        }
        int size = map.size();
        StringBuilder sb = new StringBuilder();
        int pre = -1;
        while(size-- != 0){
            char next = '#';
            int target = 0;
            for(char cur : map.keySet()){
                target = map.get(cur).get(-Collections.binarySearch(map.get(cur), pre) - 1);
                int acc = 0;
                for(char tmp : map.keySet()){
                    if(tmp == cur) continue;
                    List<Integer> list = map.get(tmp);
                    if(list.get(list.size() - 1) > target)
                        acc++;
                }
                if(acc == size){
                    pre = target;
                    sb.append(cur);
                    next = cur;
                    break;
                }
            }
            map.remove(next);
        }
        return sb.toString();
    }
}
using stack:
class Solution {
    public 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']++;
        }
        Stack<Character> st = new Stack<>(); // 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.peek() && res[st.peek()-'a']!=0){ 
                visited[st.pop()-'a']=false;
            }
            st.push(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.insert(0,st.pop());
        }
        return sb.toString();
    }
}