leetcode 每日一题：316. 去除重复字母

from collections import Counter

# https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/ 和这个题一模一样


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        if not s:
            return s

        # 基本思想，首先统计每个字母出现的次数
        # 依次填入，每次可选择当前填入之后，前面的元素是丢弃还是保留
        # 如果前面的元素后面还有剩余，即剩余出现次数大于等于1，且前面的元素比当前元素都要大，则把前面的元素移除
        cs = Counter(s)
        stack = []
        uniq = set()
        for c in s:
            if c in uniq:
                cs[c] = cs[c] - 1
                continue
            # 因为还要达到去重的效果，所以这里最后一个判断需要加uniq
            while stack and cs[stack[-1]] >= 1 and stack[-1] >= c:
                uniq.remove(stack.pop())
            cs[c] = cs[c] - 1
            stack.append(c)
            uniq.add(c)
        return "".join(stack)

https://leetcode-cn.com/problems/remove-k-digits/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/