316. Remove Duplicate Letters

Question

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

Algorithm

This question is not hard if it only requires you to remove duplicates. But it requires you to also keep the smallest lexicographical order.

I firstly use a map by hint to keep track of the count of each number but it doesn't work since we have no idea about the order info.

So, we need a map to keep the largest index of each character. The largest allows up to put larger chars in the end;

Then we need a map the record if a char is added in the sequence;

Finally, a string isn't east to handle, we use a stack to be compared with current char, if current char is smaller than the last char of the stack/temp result, and the index current char is smaller than the index of stack top, then we know the previous char is lexicographical larger than current char and can be removed since we have more later.

A example walk thought would be helpful.

Code

class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        HashSet<Character> seen = new HashSet<>();
        Map<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), i);
        }
        
        for (int i = 0; i < s.length(); i++) {
            if (!seen.contains(s.charAt(i))) {
                while (!stack.isEmpty() && s.charAt(i) < stack.peek() && i < map.get(stack.peek())) {
                    seen.remove(stack.pop());
                }
                stack.push(s.charAt(i));
                seen.add(s.charAt(i));
            }
        }
        String res = "";
        for (Character ch : stack) {
            res += ch;
        }
        return res;
    }
}