316. Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Solution:

Initiate a count array to track all the occurrences of each letters, iterate the string, once the current process letter is the last one of this character, add the smallest letter we visited so far to the solution string, and we can recursively remove duplicate letters till the end using the same technique.

 public String removeDuplicateLetters(String s) {  
     if(s==null || s.length()==0) return s;  
     int[] count=new int[26];  
     boolean[] used=new boolean[26];  
     for(int i=0;i<s.length();i++){  
       count[s.charAt(i)-'a']++;  
     }  
     int mInd=0;  
     for(int i=0;i<s.length();i++){  
       if(s.charAt(i)<s.charAt(mInd)) mInd=i;  
       if(--count[s.charAt(i)-'a']==0) break;  
     }  
     return s.charAt(mInd)+removeDuplicateLetters(s.substring(mInd+1).replaceAll(s.charAt(mInd)+"",""));  
   }