Easy understanding 10m stack java solution


  • 5
    M
    public class Solution {
       
        public static String removeDuplicateLetters(String s) {
            if (s == null || s.length() == 0){
                return "";
            }
            int[] dict = new int[26];
            // initialize
            for(int i = 0; i < s.length(); i ++){
                dict[s.charAt(i)-'a'] += 1;
            }
            Stack<Character> stack = new Stack<Character>();
            int i = 0;
            
            // maintain the sequence, if the next character is better, push it into stack
            while(i < s.length()){
                char current = s.charAt(i);
                int index = current - 'a';
                // only take care of new characters that are not in the stack
                if(!stack.contains(current)) {
                    while (!stack.isEmpty() && current <= stack.peek() && dict[stack.peek()-'a'] >= 1){
                        stack.pop();
                    }
                    if(!stack.contains(current)) {
                        stack.push(current);
                    }
                }
                dict[index]--;
                i++;
            }
            
            // convert stack to result
            StringBuilder result = new StringBuilder();
            while(!stack.isEmpty()){
                result.append(stack.pop());
            }
            return result.reverse().toString();
        }
    }

  • 0
    R

    What is the complexity incurred with stack.contains operation?


  • 0
    M

    Hi Rahul,

    In theory the stack.contains should run O(n). (Reference: http://bigocheatsheet.com/). I didn't find detailed information how java implement it, but I assume it should also be O(n).

    So Yes, this is a good point that stack.contains takes unnecessary time here instead of using other method to detect which element is already been processed.


  • 0
    X

    thanks for sharing your thought.
    Just try to make code shorter, it's not necessary to check stack contains again before !stack.contains(current)


  • 0
    S

    Nice solution! And I believe if you convert s to char[] instead of calling .charAt(i) n times will boost your performance a little bit at least.


  • 0
    C

    said in Easy understanding 10m stack java solution:

    if(!stack.contains(current)) {

    after while loop is not needed. But this solution is very nice and easy to read. Good Job!


Log in to reply
 

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