Java solution using Stack with comments


  • 97
    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.


  • 14
    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();
        
        }
    }

  • 13

    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.


  • 1
    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 :)


  • 0
    I

    Similar idea with some optimization (not using boolean array)

    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        Stack<Integer> st = new Stack<>();
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (cnt[i] < 0) {
                cnt[i]++;
                continue;
            }
            while (!st.isEmpty()) {
                if (i < st.peek() && cnt[st.peek()] * -1 > 1) {
                    int v = st.pop();
                    cnt[v] *= -1;
                    cnt[v]--;
                } else {
                    break;
                }
            }
            cnt[i] *= -1;
            st.push(i);
        }
        StringBuilder sb = new StringBuilder();
        while (!st.isEmpty()) {
            sb.append((char)(st.pop() + 'a'));
        }
        return sb.reverse().toString();
    }

  • 0
    F

    Brilliant!! So it's actually a type of monotonic stack thought, an increasing stack!!


  • 0
    M

    Brilliant solution! One nicpik:
    You probably shouldn't use sb.insert(0,st.pop()), since insert at head is O(n2) and defeats the purpose of StringBuilder.

    Could just append, then sb.reverse(), to make last string construction from O(n2) to O(n).


  • 0
    C

    wonderful solution,thank you!


Log in to reply
 

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