日常刷题(23)

1. 去除重复字母

1.1. 题目描述

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

1.2. 示例

示例 1：

输入：s = “bcabc”
输出：“abc”

示例 2：

输入：s = “cbacdcbc”
输出：“acdb”

1.3. 题目解析

直接看的答案：

1. 统计所有的字符出现次数，记为字符余量
2. 遍历s，每次取一个字符char，并在字符余量中减去1。
3. 如果stack不为空、stack[-1] < char、stack[-1]在后面还有，则用char替换最后一位

1.4. 代码

from collections import Counter

class Solution:
    def __call__(self, s: str):
        cnt = Counter(s)
        stack = []
        for char in s:
            cnt[char] -= 1

            if char in stack:
                continue

            while stack and stack[-1] > char and cnt[stack[-1]]:
                stack.pop()

            stack.append(char)

        return ''.join(stack)