@@ -0,0 +1,1853 @@
+package advanced.greedy.lc316_removeduplicateletters;%0A%0Aimport java.util.Stack;%0A%0A/**%0A * Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once.%0A * You must make sure your result is the smallest in lexicographical order among all possible results.%0A * Example:%0A *  Given %22bcabc%22, Return %22abc%22%0A *  Given %22cbacdcbc%22, Return %22acdb%22%0A */%0Apublic class Solution %7B%0A%0A    public static void main(String%5B%5D args) %7B%0A        System.out.println(new Solution().removeDuplicateLetters(%22cbbba%22));%0A    %7D%0A%0A    // Intuitive idea: when you found a smaller char, try to remove previous char if they're duplicates%0A    // Given %22bcabc%22, when you see a 'b', keep it and continue with the search, then keep the following 'c',%0A    // then we see an 'a'. Now we get a chance to get a smaller lexi order, you can check if after 'a', there is still 'b' and 'c' or not.%0A    // O(MN) time: M is size of alphabet, like O(26*N) for this problem.%0A    // pre: stack holding previous char%0A    // post: how many char left after cur position%0A    // dup: if char is already on stack (in result)%0A    public String removeDuplicateLetters(String s) %7B%0A        int%5B%5D post = new int%5B256%5D;  // All lowercase, but for clarity%0A        for (char c : s.toCharArray()) post%5Bc%5D++;%0A%0A        boolean%5B%5D dup = new boolean%5B256%5D;%0A        Stack%3CCharacter%3E pre = new Stack%3C%3E();%0A        for (char c : s.toCharArray()) %7B%0A            post%5Bc%5D--;%0A            if (dup%5Bc%5D) continue;%0A            while (!pre.isEmpty() && c %3C pre.peek() && post%5Bpre.peek()%5D %3E 0)%0A                dup%5Bpre.pop()%5D = false;%0A            pre.push(c);%0A            dup%5Bc%5D = true;%0A        %7D%0A%0A        StringBuilder ret = new StringBuilder();%0A        for (char c : pre) ret.append(c); // Nice! Java's Stack iterates from the bottom of the stack%0A        return ret.toString();%0A    %7D%0A%0A%7D%0A

leetcode-316 remove duplicate letters