题目来源

• leetcode：316. 去除重复字母

题目描述

class Solution {
    
public:
    string removeDuplicateLetters(string s) {
    

    }
};

题目解析

思路

class Solution {
    
public:
    string removeDuplicateLetters(string s) {
    
        std::string stk;
        // 首先，我们要记录字符串中每个字符出现的次数（在遍历中，每次容器移除字母时，需要减去相应字母的出现次数）。
        std::vector<int> cnt(26);
        for(auto a: s){
    
            ++cnt[a - 'a'];
        }

        for(auto a : s){
    
            // 遇到一个新字符 如果比栈顶小 并且在新字符后面还有和栈顶一样的 就把栈顶的字符抛弃了
            if (stk.find(a) == std::string::npos){
    
                // b
                while(!stk.empty() && cnt[stk.back()-'a'] > 0 && stk.back() > a)
                {
    
                    stk.pop_back();
                }
                stk.push_back(a);
            }
            // 当前遍历的字母在容器中已经出现过，将该字母次数减1， 进行下一次遍历。
            --cnt[a - 'a'];
        }

        return stk;
    }
};

思路

题目：

• 要求一、要去重。
• 要求二、去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序。
• 要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。

上述三条要求中，要求三可能有点难理解，举个例子。

比如说输入字符串 s = “babc”，去重且符合相对位置的字符串有两个，分别是 “bac” 和 “abc”，但是我们的算法得返回 “abc”，因为它的字典序更小。

按理说，如果我们想要有序的结果，那就得对原字符串排序对吧，但是排序后就不能保证符合 s 中字符出现顺序了，这似乎是矛盾的。

现在我们只实现要求一和要求二

怎么实现呢？

class Solution {
    
public:
    string removeDuplicateLetters(string s) {
    
        std::stack<char> stk; // 存放去重的结果
        // 布尔数组初始值为 false，记录栈中是否存在某个字符
        // 输入字符均为 ASCII 字符，所以大小 256 够用了
        std::vector<bool> inStack(256, false);

        for(char c : s){
    
            if(inStack[c]){
    
                continue;
            }
            stk.push(c);
            inStack[c] = true;
        }

        std::string sb;
        while (!stk.empty()){
    
            sb.insert(sb.begin(), stk.top()); stk.pop();
        }
        return sb;
    }
};

此时已经满足要求一和要求二了，如果输入 s = “bcabc”，这个算法会返回 “bca”，已经符合要求一和要求二了，但是题目希望要的答案是 “abc” 对吧。

那我们想一想，如果想满足要求三，保证字典序，需要做些什么修改？

类似题目

• 316. 去除重复字母(困难)
• 321. 拼接最大数(困难)
• 402. 去掉K位数字(中等)
• 1081. 不同字符的最小子序列（中等）