# \[316]\[困难]\[贪心]\[栈] 去除重复字母

## 题目描述

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

```
示例 1:

输入: "bcabc"
输出: "abc"
```

示例 2:

```
输入: "cbacdcbc"
输出: "acdb"
```

## 解题思路

依旧是贪心算法, 根据一定的判据逻辑, 确定每一步对应的字符是否应该被删除. 由于**字典序**以及**每个字母只能出现一次**的要求, 则在判断是否删除保留时, 如果这个字母比之前的字母更小, 而且之前的这个字母在后面也会出现, 就可以把这个字母删除掉, 否则不能删除.

为此, 我们需要:

* 一个哈希表, 记录每个字母最后一次出现的位置, 用来判断是否后面还会出现
* 另一个哈希表, 用来记录现有的子序列中有什么字母, 重复的不记录

具体步骤:

* 建立一个字典。记录每个字母最后一次出现的位置, 用来判断是否后面还会出现
* 从左往右遍历字符串
* 对于每一个字符，如果它后面还会出现，我们可以选择丢弃（也可以选择不丢弃），否则不可以丢弃。
* 是否丢弃的标准为如果栈中相邻的元素字典序更大，那么我们选择丢弃这个更大的栈中的元素。

```python
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        seen = set()
        last = {c: i for i, c in enumerate(s)}

        for i, c in enumerate(s):
            if c not in seen:
                while stack and stack[-1] > c and last[stack[-1]] > i:
                    t = stack.pop()
                    seen.discard(t)
                stack.append(c)
                seen.add(c)
        return ''.join(stack)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/316-qu-chu-zhong-fu-zi-mu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.