0316：去除重复字母（★）

2015-11-12 约 339 字预计阅读 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 相同

相似问题：

2030：含特定字母的最小子序列（2561 分）

分析

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

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        A = [ord(c)-ord('a') for c in s]
        ct = [0]*26
        for a in A:
            ct[a] += 1
        vis = [0]*26
        sk = []
        for a in A:
            ct[a] -= 1
            if vis[a]:
                continue
            while sk and sk[-1]>a and ct[sk[-1]]:
                vis[sk.pop()] = 0
            vis[a] = 1
            sk.append(a)
        return ''.join(chr(a+ord('a')) for a in sk)

0 ms

目录

0316：去除重复字母（★）

题目

分析

解答