去除重复字母

题目链接

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters相同

示例:

输入：s = "bcabc"
输出："abc"

思路

解法一：

题目要求每个字母只能出现一次，顺序不能打乱，且返回的字典序最小。

  1. 先统计每个字母个数，控制每个字母出现的次数；
  2. 使用单调栈控制字母顺序，当已经存在于栈中时，则不入栈，所以需要记录是否在栈中出现；
  3. 在弹出栈顶字符时，如果字符串在后面的位置上再也没有这一字符，则不能弹出栈顶字符。
class Solution {

public:
    string removeDuplicateLetters(string s) {
        vector<int> visit(26), num(26);
        for (char ch: s) {
            num[ch - 'a']++;
        }
        string stk;

        for (char ch : s) {
            if (!visit[ch - 'a']) { // ch之前未出现
                while (!stk.empty() && stk.back() > ch) { // 栈不为空及栈顶的字典序大于ch
                    if (num[stk.back() - 'a'] > 0) //当栈顶元素不止存在一个时
                    {
                        visit[stk.back() - 'a'] = 0; //重置访问标志
                        stk.pop_back(); // 出栈
                    }else { //当值为0，不能再弹出
                        break;
                    }
                }
            
                visit[ch - 'a'] = 1; // 设置访问标志
                stk.push_back(ch); // 入栈
            }
            num[ch - 'a'] -= 1; //出现次数减1
        }
        return stk;
    }
};