> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/zhan/316-qu-chu-zhong-fu-zi-mu.md).

# \[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)
```