solution.md

# 去除重复字母

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

<p><strong>注意：</strong>该题与 1081 <a href="https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters">https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters</a> 相同</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong><code>s = "bcabc"</code>
<strong>输出<code>：</code></strong><code>"abc"</code>
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong><code>s = "cbacdcbc"</code>
<strong>输出：</strong><code>"acdb"</code></pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= s.length <= 10<sup>4</sup></code></li>
	<li><code>s</code> 由小写英文字母组成</li>
</ul>

<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    string s = "cbacdcbc";
    string res = sol.removeDuplicateLetters(s);
    cout << res;

    return 0;
}
```

## 答案

```c

class Solution
{
public:
    string removeDuplicateLetters(string s)
    {
        int count[26] = {0};
        for (int i = 0; i < s.length(); i++)
            count[s[i] - 'a']++;
        int pos = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] < s[pos])
                pos = i;
            if (count[s[i] - 'a'] == 0)
                break;
        }
        string suffix;
        if (pos + 1 > s.length())
            suffix = "";
        else
            suffix = s.substr(pos + 1, s.length() - pos - 1);
        return s.length() == 0 ? "" : s[pos] + removeDuplicateLetters(removeOneLetter(suffix, s[pos]));
    }
    string removeOneLetter(string s, char ch)
    {
        while (1)
        {
            int index = s.find(ch);
            if (index != -1)
                s = s.erase(index, 1);
            else
                break;
        }
        return s;
    }
};
```
## 选项

### A

```c
class Solution
{
public:
    string removeDuplicateLetters(string s)
    {
        unordered_map<char, int> mp;
        unordered_map<char, bool> isIn;
        int len = s.length();
        for (int i = 0; i < len; i++)
        {
            mp[s[i]]++;
            isIn[s[i]] = false;
        }
        stack<char> ans;
        for (int i = 0; i < len; i++)
        {
            if (ans.empty())
            {
                ans.push(s[i]);
                isIn[s[i]] = true;
            }
            else if (!isIn[s[i]])
            {
                while (!ans.empty() && s[i] < ans.top())
                {
                    if (mp[ans.top()])
                    {
                        isIn[ans.top()] = false;
                        ans.pop();
                    }
                    else
                        break;
                }
                ans.push(s[i]);
                isIn[s[i]] = true;
            }
            mp[s[i]]--;
        }
        string ansS;
        while (!ans.empty())
        {
            ansS += ans.top();
            ans.pop();
        }
        reverse(ansS.begin(), ansS.end());
        return ansS;
    }
};
```

### B

```c
class Solution
{
public:
    string removeDuplicateLetters(string s)
    {
        string ans;
        for (int i = 0; i < s.size(); i++)
        {
            if (ans.find(s[i]) != string::npos)
                continue;
            for (int j = ans.length() - 1; j >= 0; j--)
            {
                if (ans[j] > s[i] && s.find(ans[j], i + 1) != string::npos)
                {
                    ans.erase(j);
                    continue;
                }
                break;
            }
            ans += s[i];
        }
        return ans;
    }
};
```

### C

```c

class Solution
{
public:
    string res = "0";
    string removeDuplicateLetters(string s)
    {
        int count[26] = {0};
        int visited[26] = {0};
        for (int i = 0; i < s.size(); ++i)
            ++count[s[i] - 'a'];
        for (const auto &c : s)
        {
            --count[c - 'a'];
            if (visited[c - 'a'] == 1)
                continue;
            while (c < res.back() && count[res.back() - 'a'])
            {
                visited[res.back() - 'a'] = 0;
                res.pop_back();
            }
            res += c;
            visited[c - 'a'] = 1;
        }
        return res.substr(1);
    }
};
```