Java Deque Solution beats 90%


  • 0
    S
        public String removeDuplicateLetters(String s) {
            if (s.isEmpty()) return "";
            
            int[] map = new int[26];
            boolean[] visited = new boolean[26];
            for (char c : s.toCharArray()) {
                map[c - 'a']++;
            }
            
            Deque<Character> stack = new LinkedList<>();
            for (char c : s.toCharArray()) {
                if (visited[c - 'a']) {
                    map[c - 'a']--;
                    continue;
                }
                
                while (!stack.isEmpty() && stack.peekLast() > c) {
                    char toRemove = stack.peekLast();
                    if (map[toRemove - 'a'] > 1) {
                        stack.pollLast();
                        map[toRemove - 'a']--;
                        visited[toRemove - 'a'] = false;
                    } else {
                        break;
                    }
                }
                
                stack.offerLast(c);
                visited[c - 'a'] = true;
            }
            
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) {
                sb.append(stack.pollFirst());
            }
            
            return sb.toString();
        }
    ···

Log in to reply
 

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