0316：去除重复字母（★）

2015-11-12 约 283 字预计阅读 1 分钟次阅读

力扣第 316 题

题目

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

示例 1：

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

示例 2：

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

提示：

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

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

分析

要字典序最小，遍历时考虑贪心
假如当前字符已采用过，跳过它
否则，假如当前字符比前一字符小，考虑删掉前一字符
- 若前一字符在后面还有，只能保留
- 否则，删掉前一字符，继续比较当前字符和前一字符

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        d = {c:i for i,c in enumerate(s)}
        sk,vis = [],set()
        for i,c in enumerate(s):
            if c not in vis:
                while sk and sk[-1]>c and d[sk[-1]]>i:
                    vis.remove(sk.pop())
                sk.append(c)
                vis.add(c)
        return ''.join(sk)

32 ms

目录

0316：去除重复字母（★）

题目

分析

解答