Remove Duplicate Letters

lc 316

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example: Given "bcabc" Return "abc"

Given "cbacdcbc" Return "acdb"

题目非常好，思路是现算出每个元素出现的次数，当当前元素比栈顶元素药小，譬如说a是当前，栈顶是b，如果b在后面还能出线的话，那么当前位当然选择a

public class Solution {



    public String removeDuplicateLetters(String s) {
    Stack<Character> stack = new Stack<>();
    int[] count = new int[26];
    char[] arr = s.toCharArray();
    for(char c : arr) {
        count[c-'a']++;
    }
    boolean[] visited = new boolean[26];
    for(char c : arr) {
        count[c-'a']--;
        if(visited[c-'a']) {
            continue;
        }
        while(!stack.isEmpty() && stack.peek() > c && count[stack.peek()-'a'] > 0) {
            visited[stack.peek()-'a'] = false;
            stack.pop();
        }
        stack.push(c);
        visited[c-'a'] = true;
    }
    StringBuilder sb = new StringBuilder();
    for(char c : stack) {
        sb.append(c);
    }
    return sb.toString();
}
  /*理解错题目了，题目的意思是在只保留一个重复元素情况下的能得到结果的最小字典序列。
    public String removeDuplicateLetters(String s) {


        if(s == null || s.length() <= 1) return s;
        TreeSet<Character> set = new TreeSet<Character>();
        for(int i = 0; i < s.length(); i++){
            set.add(s.charAt(i));
        }
        StringBuilder sb = new StringBuilder();
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            sb.append(iterator.next());
        }
        return new String(sb);
    }*/
}