Clean and Easy Understand Java Stack Solution with Explanation


  • 20
    M

    The basic idea is to go through the given string char by char. If the current char has been used in the solution string, continue our loop to next char; If not, keep replacing the last char of current solution string with our current char being considered if the current character is smaller, then add current char to solution string.

    The process requires an int array and a Boolean array to store the appearances and status(used or not) of each letter. And a stack is used to conveniently push and pop chars.

    public String removeDuplicateLetters(String s) {
    
    	Stack<Character> stack = new Stack<Character>();
    
         // appearance count
    	int[] count = new int[26];
        // used or not;
    	boolean[] added = new boolean[26];
    
        // count appearances
    	for (char ch : s.toCharArray())
    		count[ch - 'a']++;
    
        // go through each char
    	for (char ch : s.toCharArray()) {
    		
    		count[ch - 'a']--;
    		
    		if (added[ch - 'a'])
    			continue;
    
            // poping out the char which is bigger and still has some left in behind
    		while (!stack.isEmpty() && stack.peek() > ch
    				&& count[stack.peek() - 'a'] > 0)
    			added[stack.pop() - 'a'] = false;
    
           // add current one
    		stack.push(ch);
    		added[ch - 'a'] = true;
    	}
    
           // move from stack to string
    	StringBuilder sb = new StringBuilder();
    	while (!stack.isEmpty()) {
    		sb.append(stack.pop());
    	}
    
    	return sb.reverse().toString();
    
    }

  • 0
    J

    clean and fast


Log in to reply
 

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