0366MediumStringStackGreedyMonotonic Stack

Smallest Distinct Label

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def remove_duplicate_letters(s: str) -> str:

Java

public String removeDuplicateLetters(String s)

The intended approach

Time O(n)Space O(1) beyond the returned label, since the stack and the letter tables hold at most 26 entries

Note where each letter occurs for the last time, then build the label on a stack that is kept increasing where it can be. A letter already on the stack is skipped. Otherwise, while the letter on top is larger than the incoming one and also turns up again later in the code, pop it, because it can be re-collected further along and dropping it here lowers the label. Finally push the incoming letter.

Pythonentry point: remove_duplicate_letters

def remove_duplicate_letters(s):
    # One pass with a monotonic stack. O(n) time; O(1) working space beyond the
    # returned label, since the stack and the two sets hold at most 26 letters.
    last = {}
    for i, ch in enumerate(s):
        last[ch] = i
    stack = []
    taken = set()
    for i, ch in enumerate(s):
        if ch in taken:
            continue
        while stack and stack[-1] > ch and last[stack[-1]] > i:
            taken.discard(stack.pop())
        stack.append(ch)
        taken.add(ch)
    return "".join(stack)

The obvious version

Build the label one letter at a time. The next letter may be chosen from any position up to the earliest last-occurrence in what remains; take the smallest letter available in that stretch, append it, then drop everything up to and including it along with all its other copies, and repeat.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_remove_duplicate_letters(s):
    rest = s
    out = []
    while rest:
        last = {}
        for i, ch in enumerate(rest):
            last[ch] = i
        cutoff = min(last.values())
        pick = min(rest[:cutoff + 1])
        at = rest.index(pick)
        out.append(pick)
        rest = rest[at + 1:].replace(pick, "")
    return "".join(out)

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See 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