Java Stack Simulation Solution (beats 93.61% 4ms)


  • 0

    First, store the the number of each char in string and a boolean array to indicate if a char is already used.
    result[] used to simulate a stack (you can think of the size of stack is i).
    for each char in string first we do count-- (important), if it is in stack, then continue.
    while stack is not empty, and char at the top of stack < this char, pop the top and mark it unused.
    when finish, push this char and mark it used.
    Finally, return a string representing the chars in this stack.

    public class Solution {
        public String removeDuplicateLetters(String s) {
            int distinct = 0;
            int[] count = new int[26];
            boolean[] used = new boolean[26];
            char[] array = s.toCharArray();
            for (char c : array) {
                if (count[c - 'a'] == 0) {
                    distinct++;
                }
                count[c - 'a']++;
            }
            
            char[] result = new char[distinct];
            int i = 0;
            for (char c : array) {
                count[c - 'a']--;
                if (used[c - 'a']) {
                    continue;
                } else {
                    while (i > 0 && result[i - 1] > c && count[result[i - 1] - 'a'] > 0) {
                        used[result[i - 1] - 'a'] = false;
                        i--;
                    }
                    result[i++] = c;
                    used[c - 'a'] = true;
                }
            }
            
            return String.valueOf(result);
        }
    }
    

    Also, if you don't understand it. See this code:

    public class Solution {
        public String removeDuplicateLetters(String s) {
            HashMap<Character, Integer> map = new HashMap<Character, Integer>();
            HashSet<Character> set = new HashSet<Character>();
            char[] array = s.toCharArray();
            for (Character c : array) {
                if (!map.containsKey(c)) {
                    map.put(c, 1);
                } else {
                    map.put(c, map.get(c) + 1);
                }
            }
            Stack<Character> stack = new Stack<Character>();
            for (Character c : array) {
                map.put(c, map.get(c) - 1);
                if (set.contains(c)) {
                    continue;
                } else {
                    while (!stack.empty() && stack.peek() > c && map.get(stack.peek()) > 0) {
                        set.remove(stack.pop());
                    }
                    stack.push(c);
                    set.add(c);
                }
            }
            StringBuilder sb = new StringBuilder();
            while (!stack.empty()) {
                sb.append(stack.pop());
            }
            return sb.reverse().toString();
        }
    }
    

Log in to reply
 

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