316 Remove Duplicate Letters

316. Remove Duplicate Letters

1. Question

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"

2. Implementation

思路：由于题目要求输出的结果是smallest in lexicographical order among all possible results，所以考虑用单调栈保持输出结果的单调性。用两个数组count和visited表示当前字符的剩余数量和是否被拜访过，如果栈顶上的字符大于当前字符且且当前字符的剩余量不为0，说明我们现在不需要栈顶的字符，可以以后再加上保持单调性

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] count = new int[256];
        boolean[] visited = new boolean[256];
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            ++count[c];
        }

        for (char c : s.toCharArray()) {
            --count[c];

            if (visited[c]) {
                continue;
            }

            while (!stack.isEmpty() && stack.peek() > c && count[stack.peek()] != 0) {
                visited[stack.peek()] = false;
                stack.pop();
            }

            stack.push(c);
            visited[c] = true;
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.append(stack.pop());
        }
        return res.reverse().toString();
    }
}

3. Time & Space Complexity

时间和空间复杂度都是O(n)