LeetCode 316 - Remove Duplicate Letters


https://leetcode.com/problems/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"
X. Recursion
时间复杂度 O(k * n)，其中k为字符串中唯一字符的个数，n为字符串的长度

枚举字符串前缀，直到遇到首个唯一字符为止，从前缀中挑选出最小的字符作为首字符。

然后从剩余字符串中移除所有与首字母相同的字母。

重复此过程，直到选出所有唯一字符为止
https://leetcode.com/discuss/73761/a-short-o-n-recursive-greedy-solution
Given the string s, the greedy choice (i.e., the leftmost letter in the answer) is the smallest s[i], s.t. the suffix s[i .. ] contains all the unique letters.
After determining the greedy choice s[i], we get a new string s' from s by
  1. removing all letters to the left of s[i],
  2. removing all s[i]'s from s.
We then recursively solve the problem w.r.t. s'.
The runtime is O(26 * n) = O(n).
Each recursive call takes O(n), but at most 26 recursive calls will be triggered.
public String removeDuplicateLetters(String s) { int[] cnt = new int[26]; int pos = 0; // the position for the smallest s[i] for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) < s.charAt(pos)) pos = i; if (--cnt[s.charAt(i) - 'a'] == 0) break; } return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), "")); }

X. Use Stack
https://xingxingpark.com/Leetcode-316-Remove-Duplicate-Letters/
运用Stack加贪心法的题目有很多，这类问题的做法是遍历输入数组，当前元素与栈顶元素比较，如果当前元素更优（不同题目条件不同，比如本题对应当前元素较小）则pop栈顶元素，直到栈顶元素更优为止，而后插入当前元素。

使用栈（Stack）数据结构对上述算法进行优化，可以使时间复杂度缩减为O(n)
首先计算字符串s中每一个字符出现的次数，得到字典counter

遍历字符串s，记当前字符为c，将counter[c] - 1

如果c已经在栈stack中，继续遍历

将字符c与栈顶元素top进行比较，若top > c并且counter[top] > 0则弹栈，重复此过程

将c入栈
算法执行过程中，栈内元素尽可能的保持递增顺序
最后，栈中剩余元素即为所求字符串
https://discuss.leetcode.com/topic/32259/java-solution-using-stack-with-comments
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();
}
Shouldn't have used Stack because it's obsolete, ArrayDeque is better. But in this case, might as well just use the resultingStringBuilder as a stack! No boxing required, and one loop less.

sb.deleteCharAt(sb.length()-1); delete last character, but it still: - its better just use a separate stack.
if (len > 0) {
    System.arraycopy(value, start+len, value, start, count-end);
    count -= len;

}
    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();
    
    }
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
I think this solution is really concise! But I want to add some detailed explainations to show why we do so to solve the problem, This problem is in fact similiar to the problem "Largest Rectangle under the histogram "
We need to keep the monotically decreasing substring that contains all the char in the s. So we just use a vector to mimic the stack! Just similiar to the previous many solutions that use the vector to simulate a stack.
In fact this problem is also similiar to the problem that the maximum in the sliding windows, I strongly recommend you to grasp the sliding windows solutions.

public String removeDuplicateLetters(String s) {
    int[] counts = new int[26];
    boolean[] added = new boolean[26];
    if(s == null) return "";
    
    for(int i=0; i<s.length(); i++) counts[s.charAt(i) -'a']++;
    
    Stack<Character> stack = new Stack<Character>();
    for(int i=0; i<s.length(); i++) {
        char c = s.charAt(i);
        int ind = c-'a';
        
        if(stack.isEmpty()) {
            stack.push(c);
            added[ind] = true;
        } else if(!added[ind]) {
            while(!stack.isEmpty() && stack.peek() > c && counts[stack.peek()-'a'] > 0) {
                char cur = stack.pop();
                added[cur-'a'] = false;
            }
            stack.push(c);
            added[ind] = true;
        } 

        counts[ind]--;
    }
    
    
    StringBuffer str = new StringBuffer();
    while(!stack.isEmpty()) str.insert(0, stack.pop());//str.insert(0, s1.pop());
    
    return str.toString();    
}
用stack的话，最多每个字符过两遍就可以了。读字符的过程中，把字符存到stack里，当发现stack之前存的字符中比当前字符大而且频率还大于0就可以把那个字符pop出去。类似这种题目都可以用stack解决
    public String removeDuplicateLetters(String s) {
        int[] freqs = new int[256];
        
        // 统计字符频率
        for (int i = 0; i < s.length(); i++) {
            freqs[s.charAt(i)]++;
        }

        boolean[] visited = new boolean[256]; // 用来标记存在stack里的字符
        Deque<Character> q = new ArrayDeque<>();    
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freqs[c]--;
            if (visited[c]) continue;

            // pop出stack当中比当前字符大但后面还存在的的字符，
            while (!q.isEmpty() && q.peek() > c && freqs[q.peek()] > 0) {
                visited[q.pop()] = false;
            }
            q.push(c);
            visited[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (char c : q) {
            sb.append(c);
        }

        return sb.reverse().toString();
    }
  public String removeDuplicateLetters(String s) {
    if (s == null || s.length() <= 1) {
      return s;
    }

    // Step 1: find the last index for each char
    Map<Character, Integer> lastIndexMap = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      lastIndexMap.put(c, i);
    }

    // Step 2: for each character, find the smallest index in the map
    // Then find out the smallest char before the index.
    StringBuilder sb = new StringBuilder();
    int start = 0;
    int end = findSmallestIndex(lastIndexMap);

    while (!lastIndexMap.isEmpty()) {
      char curr = 'z' + 1;
      int index = 0;
      for (int i = start; i <= end; i++) {
        char c = s.charAt(i);
        if ((c < curr) && (lastIndexMap.containsKey(c))) {
          curr = c;
          index = i;
        }
      }

      // append result
      sb.append(curr);
      lastIndexMap.remove(curr);

      // update the start and end
      start = index + 1;
      end = findSmallestIndex(lastIndexMap);
    }

    return sb.toString();
  }

  private int findSmallestIndex(Map<Character, Integer> lastIndexMap) {
    int result = Integer.MAX_VALUE;
    for (int index : lastIndexMap.values()) {
      result = Math.min(result, index);
    }

    return result;

  }
虽然time complexity是O(26n) = O(n)，但实际运行起来速度比较慢，因为有很多string的操作，而我们前面也遇到过，s.substring其实已经不是O(1)的复杂度，所以会比较慢。 Discuss里另外一位rikimberley的解法就快了很多，是用数组模拟stack，还要好好体会理解。
public class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        boolean[] isCandidate = new boolean[26];
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            isCandidate[ch - 'a'] = true;
            if (--cnt[ch - 'a'] == 0) break;
        }
        for (int i = 0; i < 26; i++)
            if (isCandidate[i]) {
                char ch = (char) (i + 'a');
                for (int j = 0; j < s.length(); j++)
                    if (s.charAt(j) == ch) return ch + removeDuplicateLetters(s.substring(j + 1).replaceAll("" + ch, ""));
            }
        return "";
    }
}
https://leetcode.com/discuss/74373/java-2ms-two-pointers-solution-or-stack-simulation-beats-72%25
public String removeDuplicateLetters(String s) {
        /**
         * First loop: use an array cnt[] to count the number of times
         * appeared for each letter in s.
         *
         * Second loop (Greedy): use a stack, pop() while (!stack.isEmpty()
         * && (sc = stack.peek()) >= c && cnt[sc] > 0)
         */

        int i, n = s.length();
        int[] cnt = new int[128];
        boolean[] inRes = new boolean[128]; // whether a char is in res[]
        char[] res = s.toCharArray(); // simulate a stack

        for (i = 0; i < n; i++)
            cnt[res[i]]++;

        char c, sc;
        int end = -1;
        // now cnt[c] means the remaining count of the char c
        for (i = 0; i < n; i++) {
            c = res[i];
            if (inRes[c]) {
                cnt[c]--;
                continue;
            }

            while (end >= 0 && (sc = res[end]) >= c && cnt[sc] > 0) {
                end--;
                inRes[sc] = false;
            }

            res[++end] = c;
            cnt[c]--;
            inRes[c] = true;
        }
        return String.valueOf(res).substring(0, end + 1);
    }
https://leetcode.com/discuss/75738/java-solution-using-stack-with-comments
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();

}
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.

 -- Not really better, as sb.deleteCharAt(sb.length()-1); need copy all data: System.arraycopy(value, index+1, value, index, count-index-1);
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();

}

http://leetcode0.blogspot.com/2015/12/remove-duplicate-letters.html
就是每次从后往前数，知道全部发现string里的字符，然后在该位置i之前的字符里找到最小的char。
    public String removeDuplicateLetters(String s) {
        Set foundSet = new HashSet<Character>();
        for(char ch : s.toCharArray())
            foundSet.add(ch);
        return helper(foundSet,new StringBuffer(s));
    }
    private String helper(Set foundSet, StringBuffer buf){
        if(buf.length()==0)
            return "";
        Set set = new HashSet<Character>();
        int i = buf.length()-1 ;
        for( ;i>=0; i--){
            set.add(buf.charAt(i));
            if(set.size()== foundSet.size())
                break;
        }
        // find the min char from 0 to i; inclusive
        char ch = buf.charAt(0);
        int index = 0;
        for(int j = 1 ; j<= i ; j++)
            if(buf.charAt(j)<ch){
                ch = buf.charAt(j);
                index = j;
            }
        // delete from foundSet
        foundSet.remove(ch);
        // delete all characters before j
        buf.delete(0,index+1);
        while(buf.indexOf(""+ch)>=0){
            buf.deleteCharAt(buf.indexOf(""+ch));
        }
        return ""+ch+helper(foundSet,buf);
    }

这道题可以采用Greedy的思想，因为最后想要的结果是最小值，所以我们在满足要求的情况下把不断append最小的字符, 最后便可得到最小的字符串.
关键点就是要满足什么要求以及怎么样去满足。首先要求就是得保证在原来的字符串中存在当前字符append的顺序，即要保证每次append的字符的次数大于0。我们可以用一个数组记录每个字符出现的次数，用一个指针从左到右扫，过程中减小对应字符次数，找当前最小字符, 找的过程中终止条件是发现某个字符次数等于0，因为继续扫的话最终结果很有可能缺那个字符.
time: O(kn), space: O(k), k表示原字符串中unique字符的个数
    public String removeDuplicateLetters(String s) {
        if (s == null ||s.length() == 0)
            return s;
            
        // 记录每个字符出现的次数    
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        
        // 找出当前最小字符
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos))
                pos = i;
            
            // 避免无字符可用
            if (--cnt[s.charAt(i) - 'a'] == 0)
                break;
        }
        
        // 除去字符串中已经append的字符的所有重复值
return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }
http://traceformula.blogspot.com/2015/12/remove-duplicate-letters-leetcode.html
I. Simple Solution - O(kN) 
(Where k is the total number of distinct characters, N is length of the original string)

My first question after reading the problem description is that: What is the first character of the possible result? Can I determine it?

Yes, we can determine by an observation. If we call totalChars is the total number of distinct characters in the string. Then the required result must have a length of totalChars.  

Furthermore, its first character must be the smallest among all possible candidates. So what is a possible candidate? We easily see that a character is able to be the first character in a possible result string must have (totalChars - 1) distinct characters staying behind it in the original string.

For example, given s="bcabc", there are possible results "bca", "cab", "abc". We see that b=s[0] has 2 = totalChars-1 distinct characters behind it "a", "c".Similarly with c=s[1] and a=s[2]. Among these 3 possible candidates,  a=s[2] is the smallest. If there are 2 possible candidates with the same character, we just pick the one with smaller position.

Now after getting the first character of the result, what we do next? We can eliminate that character from the original string (by marking it as assigned). Then we repeat the process for the rest of characters!
  1. public class Solution {  
  2.   
  3.     public int ASSIGNED = -1;  
  4.     public int UNTOUCHED = 0;  
  5.     public int TOUCHED = 1;  
  6.     public char LARGE_CHAR = (char) 127;  
  7.     public String removeDuplicateLetters(String s){  
  8.         int n = s.length();  
  9.         if(n == 0) return s;  
  10.           
  11.         //We use 128 is to avoid substraction  
  12.         //if we use 26, we have to substract 'a' from a char  
  13.         int[] status = new int[128];  
  14.           
  15.         char c, smallestChar;  
  16.         int totalChars = 0;  
  17.           
  18.         for(int i=0; i<n; i++){  
  19.             c = s.charAt(i);  
  20.             if(status[c] == UNTOUCHED) totalChars++;  
  21.             status[c] = TOUCHED;  
  22.         }  
  23.           
  24.         StringBuilder bd = new StringBuilder();  
  25.         int tt = -1; //temp variable  
  26.         int last = -1; //last position of char that was assigned  
  27.           
  28.         for(int i=totalChars; i>0; i--){  
  29.             smallestChar = LARGE_CHAR;  
  30.             totalChars = 0;  
  31.               
  32.             //reset the status array  
  33.             for(int j='a'; j<='z'; j++)   
  34.                 if (status[j] == TOUCHED) status[j] = UNTOUCHED;  
  35.               
  36.             //choose the smallest candiate by running backward  
  37.             for(int j=n-1; j>last; j--){  
  38.                 c = s.charAt(j);  
  39.                 if(status[c] == ASSIGNED) continue;  
  40.                 if(status[c] == UNTOUCHED)totalChars++;  
  41.                   
  42.                 if(totalChars == i) {  
  43.                     if(c <= smallestChar){  
  44.                         smallestChar = c;  
  45.                         tt = j;  
  46.                     }  
  47.                 }  
  48.                 status[c] = TOUCHED;  
  49.             }  
  50.               
  51.             status[smallestChar] = ASSIGNED; //marked as assigned  
  52.             last = tt;  
  53.             bd.append(smallestChar);  
  54.         }  
  55.           
  56.         return bd.toString();  
  57.     }  
  58. }  
II. Better Solution - O(hN)
(Where h is a number between 1 and the total number of distinct characters)
After coming up with the above solution, I mumble "smallest candidates, smallest char, smallest possible, smallest..." . Yes, in that solution, we tried to find a smallest single character, why don't we try to find a smallest set of characters? Let's go on that direction!

We call a candidate set is a subset of distinct characters from 0 to i in the original string s so that there are still enough available characters from (i+1) to the end of string to make up totalChars distinct character.

Let's consider s="bcabc", at position 0, the candidate set is {b}. At 1, the candidate sets are {b}, {c}, {b,c}. At 2, the candidate sets are {b}, {c}, {a}, {b,c}, {c,a}, {b,c,a}. And our purpose is the same: find the smallest candidate set (by smallest, we mean lexicographically smallest). I.e, At 1, smallest candidate set is obviously {b}, at 1 it is {b}, and at 2 is {a}.


Suppose at position i, we have the smallest candidate set {a0,a1,..., ak}. Now at position i+1, what is the smallest candidate set? We know that {a0,a1,..., ak}are distinct. 

If s[i+1] already in {a0,a1,..., ak}, is it possible that there is a subset {ai0, ai1, ..., aij} so that  {ai0, ai1, ..., aij, s[i+1]} < {a0,a1,..., ak} is also a candidate set? If yes, we can easily see that {ai0, ai1, ..., aij} is a candidate set at position i, and {ai0, ai1, ..., aij} < {a0,a1,..., ak} . This means that {a0,a1,..., ak}is not the smallest candidate set at position i. Therefore, we don't need to care if s[i+1] is already in the candidate set (or we call it "assigned").

Now, if s[i+1] is not "assigned",  we have the same question - is it possible that there is a subset {ai0, ai1, ..., aij} so that  {ai0, ai1, ..., aij, s[i+1]} < {a0,a1,..., ak} is also a candidate set? If ak > s[i+1], and there are still characters that equals ak after i+1, we can remove ak and check again withak-1; if there is no more, replace it by s[i+1]. If ak < s[i+1], we cannot replace ak by s[i+1]. So we just simply add s[i+1] to the set. Simply enough?

And to represent the smallest candidate set, we can use linked list, or array. Below are 2 different implementations.

a) Using Linked List (also by array ^_^)
view plainprint?
  1. public class Solution {  
  2.   
  3.     public static char START = (char)('a'-1);  
  4.     public String removeDuplicateLetters(String s){  
  5.         if(s.length() == 0) return s;  
  6.           
  7.         //We use 128 is to avoid substraction  
  8.         //if we use 26, we have to substract 'a' from a char  
  9.         int[] count = new int[128];  
  10.         char[] prev = new char[128];  
  11.         boolean[] assigned = new boolean[128];  
  12.         char c;  
  13.         char end = START;  
  14.           
  15.         for(int i=0; i<s.length(); i++){  
  16.             c = s.charAt(i);  
  17.             count[c]++;  
  18.         }  
  19.           
  20.         for(int i=0; i<s.length(); i++){  
  21.             c = s.charAt(i);  
  22.             count[c]--;  
  23.             if(assigned[c])  
  24.                 continue;  
  25.                   
  26.             while(end >= c && count[end]>0){  
  27.                 assigned[end] = false;  
  28.                 end = prev[end];  
  29.             }  
  30.               
  31.             prev[c] = end;  
  32.             end = c;  
  33.             assigned[c] = true;  
  34.         }  
  35.           
  36.         StringBuilder bd = new StringBuilder();  
  37.         while(end>START){  
  38.             bd.append(end);  
  39.             end = prev[end];  
  40.         }  
  41.         return bd.reverse().toString();  
  42.     }  
  43. }  
b) Using array (which similar to stack)
view plainprint?
  1. public class Solution {  
  2.   
  3.     public String removeDuplicateLetters(String s){  
  4.         if(s.length() == 0) return s;  
  5.           
  6.         //We use 128 is to avoid substraction  
  7.         //if we use 26, we have to substract 'a' from a char  
  8.         int[] count = new int[128];  
  9.         char[] result = new char[26];  
  10.         boolean[] assigned = new boolean[128];  
  11.         char c;  
  12.         int end = -1;  
  13.           
  14.         for(int i=0; i<s.length(); i++){  
  15.             count[s.charAt(i)]++;  
  16.         }  
  17.           
  18.         for(int i=0; i<s.length(); i++){  
  19.             c = s.charAt(i);  
  20.             count[c]--;  
  21.             if(assigned[c])  
  22.                 continue;  
  23.                   
  24.             while(end >= 0 && result[end] > c && count[result[end]]>0){  
  25.                 assigned[result[end]] = false;  
  26.                 end--;  
  27.             }  
  28.               
  29.             end++;  
  30.             result[end] = c;  
  31.             assigned[c] = true;  
  32.         }  
  33.           
  34.         StringBuilder bd = new StringBuilder();  
  35.         for(int i=0; i<=end; i++){  
  36.             bd.append(result[i]);  
  37.         }  
  38.         return bd.toString();  
  39.     }  
  40. }  
http://bookshadow.com/weblog/2015/12/09/leetcode-remove-duplicate-letters/
贪心算法（Greedy Algorithm）
时间复杂度 O(k * n)，其中k为字符串中唯一字符的个数，n为字符串的长度
枚举字符串前缀，直到遇到首个唯一字符为止，从前缀中挑选出字典序最小的作为首字符。

然后从剩余字符串中移除所有与首字母相同的字母。

重复此过程，直到选出所有唯一字符为止。
def removeDuplicateLetters(self, s): """ :type s: str :rtype: str """ ans = '' for x in range(len(set(s))): top, idx = s[0], 0 counter = collections.Counter(s) for y in range(len(s)): if top > s[y]: top, idx = s[y], y if counter[s[y]] == 1: break counter[s[y]] -= 1 ans += top s = s[idx+1:].replace(top,'') return ans
http://fujiaozhu.me/?p=772
贪心，用栈维护，在看到Stack之前几乎无想法.. 栈中存放到当前位置为止的最优解，对于新到来的元素，如果其小于栈顶元素并且栈顶元素不是最后一次出现并且新元素未在栈中出现，就可以弹栈了，直至新元素可以加入或者判断出不需要不加入。

string removeDuplicateLetters(string s) {
string res = "";
stack<char> stk;
vector<bool> exist(26);
vector<int> sum(26), cnt(26);
for(int i = 0; i < s.size(); i ++)
sum[s[i] - 'a'] ++;
for(int i = 0; i < s.size(); i ++) {
while(!stk.empty() && s[i] <= stk.top() && cnt[stk.top() - 'a'] != sum[stk.top() - 'a'] && !exist[s[i] - 'a']) {
exist[stk.top() - 'a'] = 0;
stk.pop();
}
if(!exist[s[i] - 'a']) {
exist[s[i] - 'a'] = 1;
stk.push(s[i]);
}
cnt[s[i] - 'a'] ++;
}
while(!stk.empty()) {
res += stk.top();
stk.pop();
}
reverse(res.begin(), res.end());
return res;
}
https://leetcode.com/problems/remove-duplicate-letters/discuss/76766/Easy-to-understand-iterative-Java-solution
The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":
  1. find out the last appeared position for each letter; c - 7 b - 6 a - 2 d - 4
  2. find out the smallest index from the map in step 1 (a - 2);
  3. the first letter in the final result must be the smallest letter from index 0 to index 2;
  4. repeat step 2 to 3 to find out remaining letters.
  • the smallest letter from index 0 to index 2: a
  • the smallest letter from index 3 to index 4: c
  • the smallest letter from index 4 to index 4: d
  • the smallest letter from index 5 to index 6: b
so the result is "acdb"
Notes:
  • after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
  • in step 3, the beginning index of the search range should be the index of previous determined letter plus one
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() <= 1) return s;

        Map<Character, Integer> lastPosMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastPosMap.put(s.charAt(i), i);
        }

        char[] result = new char[lastPosMap.size()];
        int begin = 0, end = findMinLastPos(lastPosMap);

        for (int i = 0; i < result.length; i++) {
            char minChar = 'z' + 1;
            for (int k = begin; k <= end; k++) {
                if (lastPosMap.containsKey(s.charAt(k)) && s.charAt(k) < minChar) {
                    minChar = s.charAt(k);
                    begin = k+1;
                }
            }

            result[i] = minChar;
            if (i == result.length-1) break;

            lastPosMap.remove(minChar);
            if (s.charAt(end) == minChar) end = findMinLastPos(lastPosMap);
        }

        return new String(result);
    }

    private int findMinLastPos(Map<Character, Integer> lastPosMap) {
        if (lastPosMap == null || lastPosMap.isEmpty()) return -1;
        int minLastPos = Integer.MAX_VALUE;
        for (int lastPos : lastPosMap.values()) {
             minLastPos = Math.min(minLastPos, lastPos);
        }
        return minLastPos;
    }
http://www.hrwhisper.me/leetcode-remove-duplicate-letters
http://www.cnblogs.com/vision-love-programming/p/5044055.html
http://blog.csdn.net/jiangbo1017/article/details/50252525

X.
http://buttercola.blogspot.com/2016/01/leetcode-remove-duplicate-letters.html
https://discuss.leetcode.com/topic/31413/easy-to-understand-iterative-java-solution
先用哈希表记录每个字母出现的次数，再遍历给定字符串s，找出最小的字母，每比较一个字母，在哈希表中的值减1，如果此时为0了，则不继续遍历了，此时我们记录了一个位置，把字符串s中该位置左边的字符都删掉，右边的所有再出现的该字母也删掉，递归调用此函数即可，在Java中可以使用replaceAll函数
The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":
  1. find out the last appeared position for each letter;
    c - 7
    b - 6
    a - 2
    d - 4
  2. find out the smallest index from the map in step 1 (a - 2);
  3. the first letter in the final result must be the smallest letter from index 0 to index 2;
  4. repeat step 2 to 3 to find out remaining letters.
  • the smallest letter from index 0 to index 2: a
  • the smallest letter from index 3 to index 4: c
  • the smallest letter from index 4 to index 4: d
  • the smallest letter from index 5 to index 6: b
so the result is "acdb"
Notes:
  • after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
  • in step 3, the beginning index of the search range should be the index of previous determined letter plus one
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
         
        // Step 1: find the last index for each char
        Map<Character, Integer> lastIndexMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            lastIndexMap.put(c, i);
        }
         
        // Step 2: for each character, find the smallest index in the map
        // Then find out the smallest char before the index.
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int end = findSmallestIndex(lastIndexMap);
         
        while (!lastIndexMap.isEmpty()) {
            char curr = 'z' + 1;
            int index = 0;
            for (int i = start; i <= end; i++) {
                char c = s.charAt(i);
                if ((c < curr) && (lastIndexMap.containsKey(c))) {
                    curr = c;
                    index = i;
                }
            }
             
            // append result
            sb.append(curr);
            lastIndexMap.remove(curr);
             
            // update the start and end
            start = index + 1;
            end = findSmallestIndex(lastIndexMap);
        }
         
        return sb.toString();
    }
     
    private int findSmallestIndex(Map<Character, Integer> lastIndexMap) {
        int result = Integer.MAX_VALUE;
        for (int index : lastIndexMap.values()) {
            result = Math.min(result, index);
        }
         
        return result;
    }
https://discuss.leetcode.com/topic/31663/java-2ms-two-pointers-solution-or-stack-simulation-beats-99-72
public String removeDuplicateLetters(String s) {
  /**
   * First loop: use an array cnt[] to count the number of times
   * appeared for each letter in s.
   * 
   * Second loop (Greedy): use a stack, pop() while (!stack.isEmpty()
   * && (sc = stack.peek()) >= c && cnt[sc] > 0)
   */

  int i, n = s.length();
  int[] cnt = new int[128];
  boolean[] inRes = new boolean[128]; // whether a char is in res[]
  char[] res = s.toCharArray(); // simulate a stack

  for (i = 0; i < n; i++)
   cnt[res[i]]++;

  char c, sc;
  int end = -1;
  // now cnt[c] means the remaining count of the char c
  for (i = 0; i < n; i++) {
   c = res[i];
   if (inRes[c]) {
    cnt[c]--;
    continue;
   }

   while (end >= 0 && (sc = res[end]) >= c && cnt[sc] > 0) {
    end--;
    inRes[sc] = false;
   }

   res[++end] = c;
   cnt[c]--;
   inRes[c] = true;
  }
  return String.valueOf(res).substring(0, end + 1);
 }
Indeed, converting s to charArray is nice because accessing each elements in string by array is faster. In my implementation I choose to use a constant space. However I'm at the cost of accessing string (s.charAt(i)) slower. The program runs 5ms, 2.5 times slower than the original.
public String removeDuplicateLetters(String s) {
    char[] stack = new char[26];
    boolean[] inStack = new boolean[128];
    int[] cnt = new int[128];
    int top = -1, len = s.length();
    for (int i = 0; i < len; i++) cnt[s.charAt(i)]++;
    
    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        if (inStack[c]) {
            cnt[c]--;
            continue;
        }
        
        while (top >= 0 && cnt[stack[top]] > 0 && stack[top] > c)
            inStack[stack[top--]] = false;
        
        stack[++top] = c;
        inStack[c] = true;
        cnt[c]--;
    }
    
    return String.valueOf(stack, 0, top + 1);
}

X. Ordered stack
http://www.cnblogs.com/grandyang/p/5085379.html
先建立一个哈希表来统计每个字母出现的次数，还需要一个visited数字来纪录每个字母是否被访问过，我们遍历整个字符串，对于遍历到的字符，先在哈希表中将其值减一，然后看visited中是否被访问过，若访问过则继续循环，说明该字母已经出现在结果中并且位置已经安排妥当。如果没访问过，我们和结果中最后一个字母比较，如果该字母的ASCII码小并且结果中的最后一个字母在哈希表中的值不为0(说明后面还会出现这个字母)，那么我们此时就要在结果中删去最后一个字母且将其标记为未访问，然后加上当前遍历到的字母，并且将其标记为已访问，以此类推直至遍历完整个字符串s，此时结果里的字符串即为所求。这里有个小技巧，我们一开始给结果字符串res中放个"0"，就是为了在第一次比较时方便，如果为空就没法和res中的最后一个字符比较了，而‘0’的ASCII码要小于任意一个字母的，所以不会有问题。最后我们返回结果时再去掉开头那个‘0’即可
    string removeDuplicateLetters(string s) {
        int m[256] = {0}, visited[256] = {0};
        string res = "0";
        for (auto a : s) ++m[a];
        for (auto a : s) {
            --m[a];
            if (visited[a]) continue;
            while (a < res.back() && m[res.back()]) {
                visited[res.back()] = 0;
                res.pop_back();
            }
            res += a;
            visited[a] = 1;
        }
        return res.substr(1);
    }
https://discuss.leetcode.com/topic/32172/c-simple-solution-easy-understanding
 This problem is in fact similiar to the problem "Largest Rectangle under the histogram "
We need to keep the monotically decreasing substring that contains all the char in the s. So we just use a vector to mimic the stack! Just similiar to the previous many solutions that use the vector to simulate a stack.



at
Labels: , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts