8ms O(n) Java Solution


  • 2
    K

    Maintain an ArrayList with size of 26, each slot holds a LinkedList filled with the indexes of this character in input string. If the character doesn't include in the string, just fill null in ArrayList.

    from the beginning of the ArrayList, try to find a character whose first index is smaller than all characters followed in alphabets, ex. for 'a', 'b-z' should be checked, for 'd', 'e-z' should be checked. Once the character is found, append it in result. Try to iterate this steps, until all slots in ArrayList is null.

     public class Solution {
        public String removeDuplicateLetters(String s) {
            if (s == null || s.length() < 2) {
                return s;
            }
            
            ArrayList<LinkedList<Integer>> index = new ArrayList<>(26);
            for (int i = 0; i < 26; i++) {
            	index.add(null);
            }
            int n = 0;
            for (int i = 0; i < s.length(); i++) {
            	int j = (int)s.charAt(i) - (int)'a';
            	LinkedList<Integer> l = index.get(j);
            	if (l == null) {
            		l = new LinkedList<Integer>();
            		index.set(j, l);
            		n++;
            	}
            	l.add(i);
            }
            
            StringBuffer sb = new StringBuffer();
            int curr = -1;
            while (n > 0) {
            	OUT:
            	for (int i = 0; i < index.size(); i++) {
            		LinkedList<Integer> li = index.get(i);
            		if (li == null) {
            			continue;
            		}
            		while (li.peekFirst() < curr) {
            			li.pollFirst();
            		}
            		
            		for (int j = i + 1; j < index.size(); j++) {
            			LinkedList<Integer> lj = index.get(j);
            			if (lj == null || li.peekFirst() < lj.peekLast()) {
            				continue;
            			} else {
            				continue OUT;
            			}
            		}
            		
            		curr = li.peekFirst();
            		sb.append((char)('a' + i));
            		index.set(i, null);
            		n--;
            		break;
            	}
            }
            
            return sb.toString();
        }
    }

Log in to reply
 

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