Remove Duplicate Letters

Explanation & Solution

Description

Given a string s, remove duplicate letters so that every letter appears once and only once. Return the result that is the smallest in lexicographical order among all possible results.

Input: s = "bcabc"

Output: "abc"

Explanation: The unique letters are a, b, and c. The smallest lexicographical ordering using each letter once is "abc".

Constraints

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

Approach

Monotonic Stack pattern

1. Record Last Occurrences

Iterate through the string and record the last index of each character
This tells us whether a character can still appear later, so we know if it's safe to remove it from the stack

2. Initialize a Monotonic Stack and a Set

Create an empty stack to build the result
Create an inStack set to track which characters are already in the stack in O(1) time

3. Iterate Through Each Character

For each character c at index i:
If c is already in the stack, skip it — each letter must appear only once
Otherwise, proceed to the next step

4. Pop Larger Characters When Safe

While the stack is not empty, and the top of the stack is greater than c (lexicographically), and the top character appears again later (its last index > i):
Pop the top character from the stack and remove it from the inStack set
This ensures we always try to place smaller characters earlier

5. Push the Current Character

Push c onto the stack and add it to the inStack set
After processing all characters, the stack contains the answer

6. Return the Result

Join the stack into a string and return it
The stack now holds the lexicographically smallest string with all unique letters

Key Insight

The monotonic stack greedily removes characters that are larger than the current character, but only when those characters will appear again later in the string
The inStack set ensures each character is included exactly once

Time

O(n)each character is pushed and popped at most once

Space

O(1)the stack and set hold at most 26 characters (lowercase English letters)

Visualization

Input:

[b, c, a, b, c]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Sum of Subarray Ranges

Maximum Width Ramp