MediumStringStackGreedyMonotonic Stack

Remove Duplicate Letters

1 approach, code in every language

You are given a string `s`. Remove duplicate letters so that every letter appears exactly once in the result.

Among all valid results, return the one that is the smallest in lexicographic order. The relative order of the letters you keep must match their order in the original string.

Example 1

Input: s = "bcabc"

Output: "abc"

Each of a, b, and c appears once, and abc is the lexicographically smallest arrangement achievable while preserving order.

Example 2

Input: s = "cbacdcbc"

Output: "acdb"

Dropping the earlier b and c in favor of later occurrences yields acdb, which is smaller than any other valid single-copy ordering.

Constraints

1 <= s.length <= 10^4
s consists of lowercase English letters.

Greedy Monotonic Stack

Build the answer on a stack, popping a larger trailing letter whenever it still appears later, so the earliest positions get the smallest possible letters.

Loading animation…

Intuition

We want small letters as early as possible, but we can only drop a letter if it will show up again later. Precompute the last index at which each letter occurs. Walk the string keeping a stack of chosen letters; if the current letter is already on the stack, skip it. Otherwise, while the top of the stack is a larger letter that appears again after the current position, pop it because a better placement exists later. Push the current letter and mark it present. The stack read bottom to top is the lexicographically smallest valid string.

Algorithm walkthrough

1Record the last occurrence index of every character in s.
2Maintain a stack of chosen characters and a set marking which characters are currently on the stack.
3For each character c at index i, if c is already on the stack, do nothing and move on.
4Otherwise, while the stack top is greater than c and that top character appears again later (its last index is greater than i), pop it and clear it from the set.
5Push c, mark it present, and after the scan join the stack from bottom to top to form the answer.

Implementation

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

Time

O(n)

Space

O(1)

n is the length of s. Each character is pushed and popped at most once; auxiliary storage is bounded by the 26-letter alphabet.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Smallest Distinct Label is our own problem on the technique behind Remove Duplicate Letters: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free