316. 去除重复字母

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

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

示例 1：

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

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

提示：

• 1 <= s.length <= 10^4
• s 由小写英文字母组成

1.单调栈
Python解答：

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        adic = {}
        aset = set()
        for c in s:
            if c not in adic.keys():
                adic[c] = 1
            else:
                adic[c] += 1
        stack = []
        lis = list(s)
        while lis:
            c = lis.pop(0)
            if c not in aset:
                if not stack or c > stack[-1]:
                    stack.append(c)
                    aset.add(c)
                else:
                    while stack and c < stack[-1] and adic[stack[-1]] > 1:
                        adic[stack[-1]] -= 1
                        s = stack.pop()
                        aset.remove(s)
                    stack.append(c)
                    aset.add(c)
            else:
                adic[c] -= 1
        return ''.join(stack)