Share my intuitive solution using stack


  • 0
    L

    count the appearance of each character in the input;
    use a stack to maintain the result set, use a set to maintain the uniqueness;
    iterator through the input string: if the character does not exist in the result set: push the character into the result stack; otherwise keep popping the top of stack if the top is larger than the character and there is still character left to replace it. In the meanwhile, keep maintaining the count map and the set.

    public class Solution {
        public String removeDuplicateLetters(String s) {
            Map<Character, Integer> count = new HashMap<>();
            Set<Character> existed = new HashSet<>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (count.containsKey(ch)) {
                    count.put(ch, count.get(ch) + 1);
                } else {
                    count.put(ch, 1);
                }
            }
            
            Deque<Character> stack = new ArrayDeque<>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (!existed.contains(ch)) {
                    if (stack.isEmpty() || stack.peek() <= ch) {
                        stack.push(ch);
                        existed.add(ch);
                    } else {
                        while (!stack.isEmpty() && count.get(stack.peek()) > 0 && stack.peek() > ch) {
                            existed.remove(stack.peek());
                            stack.pop();
                        }
                        stack.push(ch);
                        existed.add(ch);
                    }
                }
                count.put(ch, count.get(ch) - 1);
            }
            
            StringBuilder sb = new StringBuilder();
            Iterator it = stack.descendingIterator();
            while (it.hasNext()) {
                sb.append(it.next());            
            }
    
            return sb.toString();
            
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.