Remove Duplicate Letters解题报告

Description:

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"

Link:

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

解题方法：

先统计每个字符的出现次数，然后用栈来生成结果：
从input字符串一个个读字符
1）当前字符已经在栈里面时，直接跳过本轮
2）当栈为空时或者当前字符比栈顶字符大时，直接压入栈
3）当栈顶字符比当前字符大，并且通过哈希表知道后面还有栈顶这个字符时，不断通过出栈达到条件2，再把当前字符压入栈

Time Complexity：

O(n)

完整代码：

string removeDuplicateLetters(string s) {
    unordered_map<char, int> hash;
    unordered_map<char, bool> saved;
    for(char cha: s)
        hash[cha]++;
    string result;
    for(char curr: s) {
        hash[curr]--;
        if(saved[curr])
            continue;
        while(!result.empty() && hash[result.back()] > 0 && result.back() >= curr) {
            saved[result.back()] = false;
            result.pop_back();
        }
        result += curr;
        saved[curr] = true;
    }
    return result;
}