目录

0316:去除重复字母(★)

力扣第 316 题

题目

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= s.length <= 104
  • 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