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

题目描述

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

示例 1:

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

示例 2:

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

解题思路

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

为此, 我们需要:

• 一个哈希表, 记录每个字母最后一次出现的位置, 用来判断是否后面还会出现

• 另一个哈希表, 用来记录现有的子序列中有什么字母, 重复的不记录

具体步骤:

• 建立一个字典。记录每个字母最后一次出现的位置, 用来判断是否后面还会出现

• 从左往右遍历字符串

• 对于每一个字符，如果它后面还会出现，我们可以选择丢弃（也可以选择不丢弃），否则不可以丢弃。

• 是否丢弃的标准为如果栈中相邻的元素字典序更大，那么我们选择丢弃这个更大的栈中的元素。

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)