[LeetCode] 316. Remove Duplicate Letters

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

Solution:
The hard part is the smallest in lexicographical order. So in addition to a hashmap, we also need an extra vector to label each elements for the status of visiting. First to count the appearance times for each letters in the input string. Then when scan the input string, for each new element, we need to compare it with the last letter in the output string. If the new element is smaller than the last letter in the string and also the counting for the last element is larger than 0 (which means there is still more than 0 elements in the rest part of the input string), we need to set the status of the last letter to be un-visited and remove it. Otherwise, we can add the new elements in the back of the output string and set the visiting status as true. See code below.

Code:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string res = "0";
        vector<int> m(26, 0), visit(26, 0);
        for(auto a:s) ++m[a-'a'];
        for(auto a:s){
            int t = a-'a';
            --m[t];
            if(visit[t]) continue;
            while(a<res.back() && m[res.back()-'a']){
                visit[res.back()-'a'] = 0;
                res.pop_back();
            }
            res.push_back(a);
            visit[t] = 1;
        }
        return res.substr(1);
    }
}; 

Further thinking:
How about the largest lexicographical order?
Ans: set the res to be "~" or some others that are larger than 'z'; and then change the "a<res.back()" inside the while condition into "a>res.back()". Done.

http://www.cnblogs.com/grandyang/p/5085379.html