Show problems as
Classic problem #316MediumStringStackGreedyMonotonic Stack

Remove Duplicate Letters

Real-world version: Smallest Distinct Label
Tracked in this browser only
Read Remove Duplicate Letters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstMonotonic Stack · Stacks & Queues, animated step by step

A catalogue folds a raw code s of lowercase letters down to a label.

The label has to hold every distinct letter of s exactly once, and it has to be reachable from s by deleting characters only, so the letters that survive stay in the order they had in s.

More than one label can meet both rules. Return the one that comes first in dictionary order.

Examples

Example 1

Input
s = "dbacdb"
Output
"acdb"

The distinct letters are a, b, c and d. Deleting positions 0, 1 and 5 of "dbacdb" leaves "acdb", which holds each of them once.

Example 2

Input
s = "ba"
Output
"ba"

Both letters have to appear, and the only way to keep them in their original order is "ba".

Example 3

Input
s = "zzzz"
Output
"z"

Only the letter z occurs, so the label is a single z.

Example 4

Input
s = "bcac"
Output
"bac"

Deleting the c at position 1 leaves "bac", which holds a, b and c once each.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def remove_duplicate_letters(s: str) -> str:
Java
public String removeDuplicateLetters(String s)

More on the same topics