Leetcode 316: Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters/description/

Notes:

This question is same as Leetcode 1081, which essentially asks for the same thing.

The native response is to find the smaller[i] at the most-left position first. But before the smaller s[i], when we meet with a larger letter, we need to know whether there are still some in the remaining string after the smaller[i]. If true, we can simply ignore the larger one temporally since there are still some in the remaining part.

How do we know whether there are still some in the remaining string after the smaller[i]? One way is that we can count the number of each letter firstly. Then as scanning through the string, we know exactly how many are left to each letter.

See the code below:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res = "";
        vector<int> ct(26, 0), used(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        for(auto &a : s) {
            --ct[a-'a'];
            if(used[a-'a']++ >0) continue;//once already in the res, no need to run again
            while(res.size() && res.back() > a && ct[res.back() - 'a']) {
                used[res.back() - 'a'] = 0;//once pop, is not in the res anymore
                res.pop_back();
            }
            res.push_back(a);
        }
        return res;
    }
};

Another way is to solve this problem recursively: Scan the array greedily, we need to localize the most-left smallest s[i]. But as analyzed above, the requirement for continuing the scanning of the string is that, there are still some in the remaining part of the string. Once this condition become non valid, we can

1): put s[i] into the answer;
2): remove all the elements before s[i]; (why? because there are still some after s[i])
3): remove all the rest s[i] in the remaining string;
4): recursive check the remaining string.

See the code below:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        if(s.size() < 2) return s;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        int pos = 0;
        for(int i=0; i<s.size(); ++i) {
            if(s[i] < s[pos]) pos = i; //the most-left smallest s[i];
            if(--ct[s[i]-'a'] == 0) break; //no more left in the remaining string.
        }
        for(int i=pos+1; i<s.size(); ++i) {//remove extra s[i]
            if(s[i] == s[pos]) {
                s.erase(i, 1);
                --i;
            }
        }
        return s[pos] + removeDuplicateLetters(s.substr(pos+1));
    }
};

The time complexity of the above recursive code is till O(N) or O(26*N). (each letter at most check 1 time)