Java solution, using stack with 8ms


  • 1
    A
    public static String removeDuplicateLetters(String s) {
            if(s.isEmpty() || s == null) return "";
            char[] ch = s.toCharArray();
            Stack<Character> res = new Stack<Character>();
            int[] times = new int[26];
            int n = ch.length;       //initialize the array named times which contains the times of occurrence of every letter;
            for(int i = 0; i < n; i++){
                times[ch[i]-'a']++;
            }
            
            for(int i = 0; i < n; i++){
                int index = ch[i] - 'a';
    
                times[index]--;       // whenever we get a letter, we reduce the occurrence times of it
                if(res.search(ch[i]) != -1) continue;
                                     //if the element we get now is smaller than one which is at the top of stack 
                                    //and also there are others as same as the latter
                                   //then we pop the latter from stack.
                while(!res.isEmpty() && ch[i] < res.peek() && times[res.peek() - 'a'] != 0){
                    res.pop();
                }
                res.push(ch[i]);
            }
            //output the result from stack
            int size = res.size();
            char[] resultStr = new char[size];
            while(size > 0){
                resultStr[size - 1] = res.pop();
                size--;
            }
            return String.valueOf(resultStr);
        }

  • 0
    O

    very clean solution.


Log in to reply
 

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