class Solution {
    public String removeDuplicateLetters(String s) {
        LinkedList<Character> stack = new LinkedList<>();

        Map<Character, Set<Integer>> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Set<Integer> set = map.getOrDefault(c, new HashSet<>());
            set.add(i);
            map.put(c, set);
        }
        LinkedList<Integer> indexStack  = new LinkedList<>();
        boolean[] seen = new boolean[26];

        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            while( stack.size() > 0 &&  stack.peekLast() > c && map.get(stack.peekLast()).size() > 1 && !seen[c -'a']) {
                seen[stack.peekLast() -'a'] = false;
                map.get(stack.peekLast()).remove(indexStack.removeLast());
                stack.removeLast();
            }
            if(!seen[c -'a']) {
                stack.add(c);
                seen[c -'a'] = true;
                indexStack.add(i);
            } else {
                map.get(c).remove(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(char c: stack) {
            sb.append(c);
        }
        return sb.toString();
    }
}