Remove Duplicate Letters

这道题参考完论坛上的解法，stack加贪心才是最简洁巧妙的方式。stack存储当前状态下符合要求的字符序列。贪心的核心思想和下面贪心算法一样

• 先对字符count统计。
• 遇到字符时，count－－，判断当前字符是否有被压入栈。
  • 如果没有，弹出之前栈中元素（当前字符比栈顶字符小，栈顶字符有剩余）。贪心的思想保证栈中元素总是合法的，能被压入栈中的元素要么是“字符小” 或者“”
  • 这里会出现一种情况，当前字符比栈顶字符小，而栈顶元素是唯一一个，所有栈顶元素之前的元素已经被压入并且“锁住” 后面的元素没法将栈中元素弹出，visited判断后直接跳过。
• 根据栈中元素建立字符串

public class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<Character>();
        int[] count = new int[26]; boolean[] visited = new boolean[26];
        char[] arr = s.toCharArray();

        for(char c: arr) count[c-'a']++;

        for(char c : arr){
            count[c-'a']--;
            if(visited[c-'a']) continue;
            while(!stack.isEmpty()&&c<stack.peek()&&count[stack.peek()-'a']>0){
                visited[stack.pop()-'a']=false;
            }
            stack.push(c);
            visited[c-'a']=true;
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.insert(0, stack.pop());
        }
        return sb.toString();
    }
}

六个月以前做的，都忘了。这个题有多种解法，下面是贪心的策略。

"cbacdcbc"

• 用hashmap统计每个字符最后出现的位置。c：7 b：6 a：2 d：4 ；贪心的思想是，找出“最后位置最小的”字符，比如a。因为a最后出现在2位置，我们一定要取a。依次循环。
• 找出在步骤1中 “最后位置最小的”字符，a：2.
• 第一个字符一定是在0-2之间。
• 重复步骤2-3.
  • the smallest letter from index 0 to index 2: a
  • the smallest letter from index 3 to index 4: c
  • the smallest letter from index 4 to index 4: d
  • the smallest letter from index 5 to index 6: b

public class Solution {
    public String removeDuplicateLetters(String s) {
        if(s==null || s.length()==0) return "";
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i=0;i<s.length();i++){
            map.put(s.charAt(i), i);
        }

         int start =0; int end = findMinIndex(map); char[] result = new char[map.size()];
        for(int i=0;i<s.length();i++){
            char minChar = 'z'+1;
            for(int j=start;j<=end;j++){
                if(map.containsKey(s.charAt(j)) && minChar > s.charAt(j)){
                    minChar = s.charAt(j);
                    start = j+1;
                }
            }
            result[i] = minChar;
            map.remove(minChar);
            if(i==result.length-1) break;
            if(s.charAt(end)==minChar) end = findMinIndex(map);
        }

        return new String(result);
    }

    public int findMinIndex(HashMap<Character, Integer> map){
        if (map == null || map.isEmpty()) return -1;
        int min = Integer.MAX_VALUE;
        for(int x : map.values())
            min = Math.min(min, x);
        return min;
    }
}