What is the key pattern to solve Remove Duplicate Letters efficiently?

The key pattern is stack-based state management combined with greedy lexicographical choices, ensuring each letter is added once in the minimal order.

How does GhostInterview handle duplicate tracking?

It uses sets or bit-masks to monitor which characters are already in the stack, preventing duplicates and ensuring unique inclusion.

Why is popping from the stack necessary?

Popping allows replacing larger letters with smaller ones that appear later, maintaining the lexicographical minimality required by the problem.

What is the time complexity of the solution?

The algorithm runs in O(n) time since each character is pushed and popped at most once, with membership checks in O(1) using a set or bit-mask.

Can this method be applied to similar problems?

Yes, any problem requiring unique elements in optimal order with stack-based management or greedy selection can use the same approach.

#316

Medium

auto_awesome栈·状态

LeetCode 题解工作台

去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。示例 1：输入： s = "bcabc" 输出： "abc" 示例 2：输入： s = "cbacdcbc" 输出： "acdb" 提示： 1 4 …

字符串栈贪心单调栈

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

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

lightbulb

解题思路

方法一：栈

我们用一个数组 last 记录每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 vis 或者一个整型变量 mask 记录当前字符是否在栈中。

遍历字符串 $s$ ，对于每个字符 $c$ ，如果 $c$ 不在栈中，我们就需要判断栈顶元素是否大于 $c$ ，如果大于 $c$ ，且栈顶元素在后面还会出现，我们就将栈顶元素弹出，将 $c$ 压入栈中。

最后将栈中元素拼接成字符串作为结果返回。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(k) where k is the number of unique letters, to store the stack, frequency map, and membership tracking set.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch if the candidate correctly handles repeated letters and maintains order.
question_mark
Check if they can justify the greedy lexicographical choice at each stack operation.
question_mark
Look for efficient membership tracking to prevent duplicate insertion into the stack.

warning

常见陷阱

外企场景

error
Pushing duplicates onto the stack instead of tracking existing letters.
error
Failing to pop characters when a smaller character appears later, leading to a non-optimal result.
error
Ignoring the last occurrence check, which can remove needed letters and break correctness.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify to allow uppercase letters and mixed case while still removing duplicates lexicographically.
arrow_right_alt
Return the largest lexicographical order string instead of the smallest.
arrow_right_alt
Apply the same stack-based approach to arrays of integers with unique selection constraints.

help

常见问题

外企场景

继续练习

#402 移掉 K 位数字 #1081 不同字符的最小子序列 #321 拼接最大数