LeetCode 316 Remove Duplicate Letters

    
        标签：
        
            数组类题目
        
            LeetCode
        
    发布于：2022-02-13 17:26:51
    编辑于：2022-02-13 19:09:04
    浏览量：740

概述

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

直接法

首先遍历一遍用哈希表存一下各个字母的出现次数。

然后从头开始遍历开始删除字母，对于每个字母：

如果其就存在了一次，不能删，下一个；
如果存在了多次，
1. 且之前已经保留了一次，则删，
2. 尚未被保留，则查看其后面的字母是否字典序大于等于它：
  1. 如果其后面的字母字典序更小，则删；（要是后面的字母被删了怎么办？所以我们当遇到过一次且保留后就该删掉所有其他值，起码标记一下）
  2. 否则保留。

对应代码： class Solution { public: string removeDuplicateLetters(string s) { unordered_map<char, int> m; for (auto c : s) m[c] ++; unordered_map<char, bool> alreadyKept; string ans; for (int i = 0; i < s.size(); i++) { char c = s[i]; if (m[c] == 1) { cout << c << endl; ans += c; continue; } if (alreadyKept[c]) continue; bool hasSmallerAfterThis = false; int j = i + 1; while (j < s.size()) { if (!alreadyKept[s[j]] && s[j] < s[i]) { hasSmallerAfterThis = true; break; } j ++; } if (!hasSmallerAfterThis) { ans += c; alreadyKept[c] = true; } } return ans; } };

上面的思路是有问题的，例如输入为 "cbacdcbc" 时，输出为 "adbc"，实际应为 "acdb"。

所以当遇到必须保留的值时，while 循环需要结束。

另外就是，当字符只剩下一个时，也必须保留。

改进到这里，已经是 278 / 289 test cases passed 了，但是一下情况难以应对：

Input: "bccab"
Output: "cab"
Expected: "bca"

虽然也可以继续改，但我感觉现在的解法已经是过于杂乱了，充满了判断。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> m;
        for (auto c : s) m[c] ++;
        unordered_map<char, bool> alreadyKept;
        string ans;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            cout << "i " << i << " c " << c << endl;
            if (alreadyKept[c]) continue;
            if (m[c] == 1) {
                ans += c;
                continue;
            }
            
            bool hasSmallerAfterThis = false;
            int j = i + 1;
            
            while (j < s.size()) {
                if (m[s[j]] == 1 && !alreadyKept[s[j]]) {
                    if (s[j] < s[i]) {
                        cout << s[j] << " vs " << s[i] << endl;
                        hasSmallerAfterThis = true;
                    }
                    break;
                }
                if (!alreadyKept[s[j]] && s[j] < s[i]) {
                    hasSmallerAfterThis = true;
                    break;
                }
                j ++;
            }
            cout << "hasSmallerAfterThis " << hasSmallerAfterThis << endl;
            if (!hasSmallerAfterThis) {
                ans += c;
                alreadyKept[c] = true;
            }
            m[c] --;
        }
        return ans;
    }
};

基于栈的解法

https://mp.weixin.qq.com/s/Yq49ZBEW3DJx6nXk1fMusw

大致思路：

首先遍历一遍维护一个记录字符个数的哈希表，
构造一个堆栈开始遍历字符，遍历过的字符更新哈希表，使其表示剩余未遍历部分的字符存在情况。

大体思想就是，如果合适就先压入栈，之后压入新元素时就弹出能弹掉的。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<char> ans;
        unordered_map<char, bool> inStack;
        unordered_map<char, int> count;
        for (auto c : s) count[c] ++;
        for (auto c : s) {
            count[c] --;  // 此行不能放到循环体的最后，因为有时候循环体未必能执行到最后
            if (inStack[c]) continue;
            while (!ans.empty() && ans.back() >= c) {
                if (count[ans.back()] == 0) break;
                inStack[ans.back()] = false;
                ans.pop_back();
            }
            ans.push_back(c);
            inStack[c] = true;
        }
        string res(ans.begin(), ans.end());
        return res;
    }
};

Links: leetcode-316-remove-duplicate-letters