What is the brute force approach and complexity for Remove Duplicate Letters?

Generate every subsequence with each letter once; keep the smallest with time complexity O(2^N · N) and space complexity O(N).

What is the optimal approach and complexity for Remove Duplicate Letters?

Skip letters already used; pop a bigger top only if it appears again later; push with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Remove Duplicate Letters?

Look for key signals in the prompt: "smallest in dictionary order" indicates Small letters should come early → a bigger letter before a smaller one is popped → increasing stack.; "every distinct letter exactly once" indicates Popping is only allowed if the letter comes back later (last index), and repeats are skipped (inStack).; "subsequence (original order)" indicates A left-to-right scan that keeps or drops letters, like Remove K Digits..

Remove Duplicate Letters

Medium·LeetCode #316 Pro OnlyInterview-Level

LeetCode

Problem Statement

You are given a string s of lowercase letters.

Remove letters so that every distinct letter appears exactly once. The letters you keep stay in their original order (you are choosing a subsequence).

Among all the ways to do that, return the one that is smallest in dictionary order.

(LeetCode 1081, Smallest Subsequence of Distinct Characters, is the same problem.)

Input

A string s of lowercase English letters.

Output

The smallest subsequence of s (in dictionary order) that contains each distinct letter of s exactly once.

Example 1

Input: s = "bcabc"

Output: "abc"

The letters are a, b, c. Keep the a at index 2 and the b, c after it.

Example 2

Input: s = "cbacdcbc"

Output: "acdb"

Keep the a (index 2), c (3), d (4) and b (6). Something smaller like "abcd" or "acbd" is impossible: the only d is at index 4, and no b sits between the a and that d, so the b has to come after the d.

Constraints

• 1 ≤ s.length ≤ 10^4
• `s` has only lowercase English letters

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“smallest in dictionary order”

→ Small letters should come early → a bigger letter before a smaller one is popped → increasing stack.

“every distinct letter exactly once”

→ Popping is only allowed if the letter comes back later (last index), and repeats are skipped (inStack).

“subsequence (original order)”

→ A left-to-right scan that keeps or drops letters, like Remove K Digits.

Approach Complexity Ladder

Brute Force — try every subsequenceO(2^N · N)O(N)

Generate every subsequence with each letter once; keep the smallest

Better — greedy, one letter at a timeO(26 · N)O(26)

Pick the smallest letter that still leaves every other needed letter later; repeat

Optimal — increasing stack with a "comes back later" checkO(N)O(1)

Skip letters already used; pop a bigger top only if it appears again later; push

Brute Force Intuition

For each position, either keep the letter or skip it, but never keep a letter twice. When you reach the end, the result counts only if it has every distinct letter. Keep the smallest one you find.

Recognition rule for this sub-pattern:

Need the first smaller value. Keep an increasing stack; greedy "remove bigger digits before me" problems also live here.

Remember this · Monotonic Stack

Trigger

Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"

Think

When a new element arrives, which older elements can never be the answer again?

Key question

Is my stack increasing or decreasing, and what do I record when I pop?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Remove K Digits