题解49 | #去除所有重复字母#

注意区别：题解30 | 连续重复的东西总会被消除#点击消除#https://www.nowcoder.com/discuss/536957728435064832

#include <iterator>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
        string removeDuplicateLetters(string str) {
            vector<bool> vis(26, false); // 记录每个字母是否出现过
            vector<int> count(26, 0); // 记录每个字母的出现次数

            for (char ch : str) {
                count[ch - 'a']++;
            }

            string ans; // 结果字符串

            for (char ch : str) {

                count[ch - 'a']--; // 当前字母出现次数减1

                if (vis[ch - 'a']) { // 如果当前字母已经在结果字符串中出现过，则直接跳过
                    continue;
                }
                //如果当前字母比结果字符串的最后一个字母小，并且最后一个字母在后面还会出现，
                //则将最后一个字母从结果字符串中移除
                while (!ans.empty() && ch < ans.back() && count[ans.back() - 'a'] > 0) {
                    vis[ans.back() - 'a'] = false;
                    ans.pop_back();
                }
                ans.push_back(ch); // 将当前字母加入结果字符串中
                vis[ch - 'a'] = true; // 标记当前字母已经出现过
            }

            return ans;
        }
    
};

基本算法思想：

1. 首先统计每个字母在字符串中出现的次数，并记录每个字母是否已经出现过。

2. 遍历字符串中的每个字母，如果当前字母已经在结果字符串中出现过，则直接跳过。

3. 如果当前字母比结果字符串的最后一个字母小，并且最后一个字母在后面还会出现，则将最后一个字母从结果字符串中移除。

4. 将当前字母加入结果字符串中，并标记当前字母已经出现过。

5. 返回结果字符串。

时间复杂度：

O(n)，其中n为字符串的长度，需要遍历字符串两次。

空间复杂度：

O(1)，使用了常数个额外空间。