Java solution using Stack with comments


  • 85
    D
    public String removeDuplicateLetters(String sr) {
    
        int[] res = new int[26]; //will contain number of occurences of character (i+'a')
        boolean[] visited = new boolean[26]; //will contain if character (i+'a') is present in current result Stack
        char[] ch = sr.toCharArray();
        for(char c: ch){  //count number of occurences of character 
            res[c-'a']++;
        }
        Stack<Character> st = new Stack<>(); // answer stack
        int index;
        for(char s:ch){ 
            index= s-'a';
            res[index]--;   //decrement number of characters remaining in the string to be analysed
            if(visited[index]) //if character is already present in stack, dont bother
                continue;
            //if current character is smaller than last character in stack which occurs later in the string again
            //it can be removed and  added later e.g stack = bc remaining string abc then a can pop b and then c
            while(!st.isEmpty() && s<st.peek() && res[st.peek()-'a']!=0){ 
                visited[st.pop()-'a']=false;
            }
            st.push(s); //add current character and mark it as visited
            visited[index]=true;
        }
    
        StringBuilder sb = new StringBuilder();
        //pop character from stack and build answer string from back
        while(!st.isEmpty()){
            sb.insert(0,st.pop());
        }
        return sb.toString();
    }

  • 4

    Shouldn't have used Stack because it's obsolete, ArrayDeque is better. But in this case, might as well just use the resulting StringBuilder as a stack! No boxing required, and one loop less.


  • 13
    A

    @dwaijam .. Thanks for sharing this solution. I had not been able to wrap my head around the exact requirement of the solution from the examples provided. Using the StringBuilder as a stack, the run-time reduces from 5 ms to 3 ms.

    @stachenov .. Thanks for your suggestion of using the StringBuilder as a stack.

    public class Solution {
        public String removeDuplicateLetters(String s) {
            
            int[] res = new int[26]; // will contain number of occurences of character (i+'a')
            boolean[] visited = new boolean[26]; // will contain if character ('a' + i) is present in current result Stack
            char[] ch = s.toCharArray();
            for(char c : ch){  // count number of occurences of character 
                res[c-'a']++;
            }
            StringBuilder sb = new StringBuilder();; // answer stack
            int index;
            for(char c : ch){ 
                index = c - 'a';
                res[index]--;   // decrement number of characters remaining in the string to be analysed
                if(visited[index]) // if character is already present in stack, dont bother
                    continue;
                // if current character is smaller than last character in stack which occurs later in the string again
                // it can be removed and  added later e.g stack = bc remaining string abc then a can pop b and then c
                while( (sb.length() > 0) && c < sb.charAt(sb.length()-1) && res[sb.charAt(sb.length()-1)-'a']!=0){ 
                    visited[sb.charAt(sb.length()-1) - 'a'] = false;
                    sb.deleteCharAt(sb.length()-1);
                }
                sb.append(c); // add current character and mark it as visited
                visited[index] = true;
            }
            
            return sb.toString();
        
        }
    }

  • 12

    I thought of the same approach, which is applied to another problem.

    For an in[] array, and int K, form maximum number, while maintaining order.

    Example - [2,3,9,8,2,6], and K = 3, the maximum number formed is [9,8,6].

    [2] - Add, while remaining K = 2, Remaining elements is 5

    [2,3] - Add 3, while remaining K = 1, Remaining elements is 4

    [9] - Pop 3 and 2, since 9 is greater than both and remaining K = 2 < elements = 3

    [9,8] - Add 8, less than 9, and remainging K = 1 < elements = 2

    [9,8,2] - Add 2, less than 8, and remainging K = 0 < elements = 1

    [9,8,6] - Pop 2, Add 6, since popping 2 makes K = 1, and element left is 1, which is 6


  • 0
    J

    great solution. I like it.


  • 0
    R

  • 0

    The best simple and fast solution. Thanks for sharing!


  • 0

    Love your solution which is the only one I can understand clearly... Thanks for sharing!


  • 0
    S

    To determine whether the current stack top (some char) has a later occurrence after current char (c) in the given string. We can also use an array to indicate the latest occurrence of each character.


  • 0
    T

    Great solution!. When adding a character 'c', the reason to skip it when visited[index] is true is that it is either

    • c is smaller than all characters in the stack, moving it backward make no sense
    • c is greater than certain character 'ch' in the stack. When 'ch' is added, c was in the stack but not removed. That means there is another character k where k > c > a. k is added to the stack after c and before 'ch'. When a is added, there must be only no more k left. So 'c' can not move backward.

  • 0
    T

    This is the easiest method I have ever seen!


  • 0
    C

    public String removeDuplicateLetters(String s) {

        int[] nums = new int[26];
        char []ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            nums[ch[i] - 'a']++;
        }
        boolean[] exist = new boolean[26];
        char[] result = new char[26];
        int pointer = -1;
    
        for (int i = 0; i < ch.length; i++) {
    
            if (exist[ch[i] - 'a']) {
                nums[ch[i] - 'a']--;
                continue;
            }
            while (pointer >= 0 && ch[i] < result[pointer] && nums[result[pointer]- 'a'] >= 1) {
                exist[result[pointer] - 'a'] = false;
                pointer--;
            }
            if (pointer == -1 || !exist[ch[i] - 'a']) pointer++;
            result[pointer] = ch[i];
            exist[ch[i] - 'a'] = true;
            nums[ch[i] - 'a']--;
        }
        return new String(result, 0, ++pointer);
    }
    

    Instead of using stack I use ch array to optimize the code :)


Log in to reply
 

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