力扣 316 去除重复字母

题意：给定一个字符串，返回去除重复后，安字典顺序最大的字符串

思路：具体见代码注释

思想：双向队列

复杂度：时间O（n)，空间O(n)

class Solution {
    public String removeDuplicateLetters(String s) {
        
        //store the last index for each letter
        int[] arr = new int[26];
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            arr[c-'a'] = i;
        }
        
        //keep track if letter has been added
        HashSet<Character> set = new HashSet<>();
        Deque<Character> stack = new ArrayDeque<>();
        
        for(int i = 0; i< s.length(); i++) {
            char c = s.charAt(i);
            
            //always add letter if not yet added
            if(!set.contains(c)) {
            
               //keep removing if previous letter is bigger and the letter is available later   
                while(!stack.isEmpty() && (stack.peek() > c) && (arr[stack.peek()-'a'] > i)) {
                    char tmp = stack.pop();
                    set.remove(tmp);
                }
                set.add(c);
                stack.push(c);
            }
        }
        
        //append and reverse before return
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}