ArrayDeque Java Solution beats 90%


  • 0
    S
        public String removeDuplicateLetters(String s) {
            int[] counts = new int[26];
            for (char c : s.toCharArray()) counts[c - 'a']++;
            
            ArrayDeque<Character> stack = new ArrayDeque<>();
            
            StringBuilder sb = new StringBuilder();
            boolean[] visited = new boolean[26];
            for (char c : s.toCharArray()) {
                if (!visited[c - 'a']) {
                    while (!stack.isEmpty() && c < stack.peekLast() && counts[stack.peekLast() - 'a'] > 1) {
                        counts[stack.peekLast() - 'a']--;
                        visited[stack.pollLast() - 'a'] = false;
                    }
                    
                    stack.addLast(c);
                    visited[c - 'a'] = true;
                } else {
                    counts[c - 'a']--;
                }
            }
            
            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.