Java O(n) time O(1) space using Stack


  • 2
    public class Solution {
        public String removeDuplicateLetters(String s) {
            if (s == null || s.isEmpty())
                return "";
            Stack<Character> stack = new Stack<>();
            Map<Character, Integer> map = new HashMap<>();
            for (char c : s.toCharArray()) {
                int count = map.containsKey(c) ? map.get(c) : 0;
                map.put(c, count + 1);
            }
            Set<Character> inStack = new HashSet<>();
            for (char c : s.toCharArray()) {
                if (inStack.contains(c)) {
                    map.put(c, map.get(c) - 1); 
                    continue;
                }
                while (!stack.isEmpty()) {
                    char top = stack.peek();
                    if (map.get(top) > 1 && c < top) {
                        stack.pop();
                        inStack.remove(top);
                        map.put(top, map.get(top) - 1);
                    } else {
                        break;
                    }
                }
                stack.push(c);
                inStack.add(c);
            }
            String res = "";
            while (!stack.isEmpty()) {
                res = stack.pop() + res;
            }
            return res;
        }
    }
    

    use map to count number of occurrences of each letter. O(1) space
    since there are at most 26 letters and O(n) time.
    use stack to store letters in ascending lexicographic order. for every char c, we pop top letter in the stack which is bigger and has more than 1 count. Push c in the stack if it is not already in the stack. we need hashset to keep track if each letter is in the stack. Any suggestions to improve the code?


  • 0

    Why is this O(1) space when you are using map and stack?


Log in to reply
 

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