Leetcode 1081: Smallest Subsequence of Distinct Characters

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/description/

Notes:

This question is the same as another question Leetcode 316. Please refer to that post for the analysis.

Here two other methods are shared below.

The first one is by analyze the indexes of all the letter. The basic logic is that: start with the smallest letter, if its first index is smaller than all the last indexes of all the rest letters, then it definitely will be the first one to choose. If the smallest does not fit with this condition, meaning there are some larger letter ends earlier than it. So we simply move on to the second smallest one, and so on.

Once we find the first letter, we need to update the indexes. Basically, all the indexes of this letter will not be considered any more; and all the indexes of all the rest letters which are smaller than chosen index can be removed. There is no need to consider them more.

See the code below:

class Solution {
public:
    string smallestSubsequence(string text) {
        string res = "";
        vector<vector<int>> ids(26);//the indexes of letter
        int ct = 0;//the number of unique letters
        for(int i=0; i<text.size(); ++i) {
            if(ids[text[i]-'a'].empty()) ++ct;
            ids[text[i]-'a'].push_back(i);
        }
        vector<int> used(26, 0);//label whether in the res or not
        while(ct>0) {
            int last_min = 1001;// the minimum of the last index of each letter
            for(int i=0; i<26; ++i) {
                if(ids[i].empty() || used[i]) continue;
                last_min = min(last_min, ids[i].back());
            }
            int pos = 0;
            for(int i=0; i<26; ++i) {//find the samllest letter shows on the left of all the rest letters
                                     //or the smallest letter whose smallest index is smaller than
                                     //all the last indexes of all the rest letters
                if(ids[i].empty() || used[i]) continue;
                if(ids[i].front()<=last_min) {
                    pos = i;
                    break;
                }
            }
            res.push_back(pos+'a');
            used[pos] = 1;
            for(int i=0; i<26; ++i) {//remove all the indexes which are smaller than ids[pos].front()
                if(ids[i].empty() || used[i]) continue;
                while(ids[i].size() && ids[i].front() < ids[pos].front()) ids[i].erase(ids[i].begin());
            }          
            --ct;
        }
        return res;
    }
};

So one thing from the above code can be seen is that the last index of each letter is important. Follow this line, we can develop another solution.

Let find the last index of each letter first.

Then scan the string. For each letter, we just need to check the range of current position to its last index.

If there is a smaller letter found between, meaning the smaller letter can be before the current letter; so give up the current letter temporally;

If there is a larger letter found between, we need to consider two situations:

one is that the last index of the larger letter is larger than that of the current letter. For this case we just can continue, because the larger letter will show up latter;

the other case is the opposite, meaning that the larger letter ends up earlier than the current letter. In this case, we need to shorten the search range, because the early termination of a larger letter means that we have to stop to take the larger letter in the final result before going to further. Of course, the current letter which is smaller should be put before the larger letter.

See the code below:

class Solution {
public:
    string smallestSubsequence(string text) {
        string res = "";
        int len = text.size();
        vector<int> ct(26, -1);
        for(int i=0; i<text.size(); ++i){
            ct[text[i]-'a'] = i;
        }
        for(int i=0; i<text.size(); ++i){
            int right = ct[text[i]-'a'];
            if(right == -1) continue;
            bool find = true;
            for(int j=i+1; j<right; ++j){
                if(ct[text[j]-'a'] == -1 || text[j] == text[i]) continue;
                if(text[j] > text[i] && ct[text[j]-'a'] < right) right = ct[text[j]-'a'];
                if(text[j] < text[i]) {find = false; break;}
            }
            if(find) {res.push_back(text[i]); ct[text[i]-'a'] = -1;}
        }
        return res;
    }
};