316. Remove Duplicate Letters ---- M ~~~~~~~~~

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

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

 

Example 1:

Input: s = "cdadabcc"
Output: "adbc"

Example 2:

Input: s = "abcd"
Output: "abcd"

Example 3:

Input: s = "ecbacba"
Output: "eacb"

Example 4:

Input: s = "leetcode"
Output: "letcod"

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

A:
就是每次从后往前数，知道全部发现string里的字符，然后在该位置i之前的字符里找到最小的char。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    string removeDuplicateLetters(string s) {
        int flag = 0;
        for(char ch : s){
            flag |= 1<<(ch-'a');
        }
        return helper(s,0, flag);
    }
private:
    // count backward, until we find all chars, then find all 
    string helper(string s, int start, int flag){// flag[i] == 0, means i+'a' need to be found
        if (start >= s.length() || flag ==0){ // stop condition
            return "";
        }
        int newFlag = 0;
        int i = s.size()-1;
        for( ; i>=start;i--){
            int mask = 1<<(s[i] -'a');
            if(mask & flag){// if exist
                newFlag |= mask;
            }
            if(newFlag == flag){
                break;
            }
        }
        // find the minChar;
        char minChar = s[i];
        int minIndex = i;
        for (int j = i-1; j >=start; j--) {
            int mask = 1<<(s[j] - 'a');
            if(mask&flag){
                if(s[j] <= minChar){
                    minChar = s[j];
                    minIndex = j;
                }
            }
        }
        flag -= 1<< (minChar - 'a');
        return string(1,minChar)+helper(s,minIndex+1,flag);
    }
};

Mistakes:

1: helper() 里没有做stop condition 检测。  

而且后来也没有做flag ==0 的检测

2：Line 30,  应该是从后向前检测的。  然而我写成从前向后了。 该死

3：同样的， line 33 ,应该有等号。

4： line 6, 第一遍写错了。写成了加号。  该死

***************第二遍的时候， 用了记录所有的位置 。然后每次寻找左右发生的最后一个位置。 并在所有char的最先一个位置。*****然而，速度才超过了22%.上面的超过97%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public: string removeDuplicateLetters(string s) { unordered_map<char,vector<int>> M; for(int i =s.length()-1; i>=0; i--){ M[s[i]].push_back(i); } string res=""; while(not M.empty()){ //among the last appearance index of 'a'->'z', find the minIndex int minLastIndex = s.length()-1; for(char ch = 'a';ch<='z'; ch++){ if(M.find(ch) != M.end()){ minLastIndex = min(minLastIndex, M[ch].front()); } } // now among all values, if it is bool findMinChar=false; int deletedIndex = 0; for(char ch = 'a';ch<='z'; ch++){ if(M.find(ch) != M.end() ){ if(not findMinChar && ( M[ch].back() <= minLastIndex)){ res+= ch; deletedIndex = M[ch].back(); M.erase(ch); findMinChar = true; continue; } if(findMinChar ){ while((not M[ch].empty()) && M[ch].back()<deletedIndex){ M[ch].pop_back(); } if(M[ch].empty()) M.erase(ch); } } } } return res; } };