Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/description/

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"

Thoughts

题目的意思是每个字符只保留一个，并且在维持原来字符相对位置的前提下，选保留能使string是个升序序列，前面元素尽量小。

比如[abc]就比[bac]小。

看到保留升序想到stack。我们能想到当遇到新元素比stack中top小时，把stack中元素抛出。但因为每个元素都要保留至少一次，我们抛掉后这个元素就没有了怎么办？因此我们需要amount map帮助我们判断还能抛否，如果amount[top] == 0就代表不能抛了。我们只能让它固定在那。然后把新元素插入栈即可。

当一个元素固定在一个位置，即使后面还出现了stack排在该元素前面的元素，我们也要一律作为没看到。比如[cdc], 我们把d固定后，即使后面还有c，由于d不能动了，为了使得最后的结果尽量升序前面的元素尽量小([cd]比[dc])小，我们需要无视第二个c，不能让它继续插入。因此还需要一个visited的set记录当前栈内都有了谁。

Code

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] amount = new int[26];
        boolean[] visited = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            amount[c - 'a']++;
        }

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (amount[c - 'a'] > 0 && !visited[c - 'a']) {
                while (!stack.isEmpty() && amount[stack.peek() - 'a'] > 0 && stack.peek() > c) {
                    visited[stack.pop() - 'a'] = false;
                }
                stack.push(c);
                visited[c - 'a'] = true;
            } 
            amount[c - 'a']--;
        }

        String res = "";
        for (Character c : stack) {
            res = res + c;
        }

        return res;
    }
}

Analysis

Errors:

1. 没用visited, 全用的amount map。导致逻辑有些乱

时空复杂度都是O(N).