Remove Duplicate Letters

MediumMonotonic Stack · Greedy🧩 Stack LeetCode #316 ↗Updated Oct 30, 2026

Problem

Given a lowercase string s, delete characters so that every distinct letter appears exactly once. Among all such results (each is a subsequence of s), return the lexicographically smallest one.

Input"bcabc"Output"abc"

Input"cbacdcbc"Output"acdb"

1 ≤ s.length ≤ 10⁴ · s has only lowercase English letters · Same as LC 1081

Try it yourself

Java

class Solution {
    public String removeDuplicateLetters(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Build the answer left to right and keep it as small as possible: a bigger letter on top can be popped for a smaller incoming one only if it appears again later, so it can still be placed afterwards.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForceTry Every Valid Subsequence

Time O(2ⁿ·n)Space O(n)

Backtrack over each index: take s[i] (if its letter is unused) or skip it. Whenever the built string has all k distinct letters, compare it with the best so far. Exhaustive, so trivially correct.

Java

private String best;

public String removeDuplicateLetters(String s) {
    best = null;
    int k = (int) s.chars().distinct().count();
    build(s, 0, new StringBuilder(), new boolean[26], k);
    return best;
}

private void build(String s, int i, StringBuilder cur, boolean[] used, int k) {
    if (cur.length() == k) {
        if (best == null || cur.toString().compareTo(best) < 0) best = cur.toString();
        return;
    }
    if (i == s.length()) return;
    int c = s.charAt(i) - 'a';
    if (!used[c]) {                               // take s[i]
        used[c] = true;
        cur.append(s.charAt(i));
        build(s, i + 1, cur, used, k);
        cur.deleteCharAt(cur.length() - 1);
        used[c] = false;
    }
    build(s, i + 1, cur, used, k);                // skip s[i]
}

Correct by definition, but exponential — only usable for tiny inputs.

BetterGreedy: Pick Smallest Safe First Letter

Time O(k·n)Space O(k·n)

The first letter of the answer is the smallest one we can take without losing any letter: scan until some letter's last occurrence and pick the smallest letter in that prefix. Then drop that letter everywhere and recurse on the rest. k ≤ 26 distinct letters ⇒ at most k levels.

Java

public String removeDuplicateLetters(String s) {
    if (s.isEmpty()) return "";
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) cnt[c - 'a']++;
    int pos = 0;                                  // smallest letter in the safe prefix
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) < s.charAt(pos)) pos = i;
        if (--cnt[s.charAt(i) - 'a'] == 0) break; // s[i] never appears again
    }
    char c = s.charAt(pos);
    String rest = s.substring(pos + 1).replace(String.valueOf(c), "");
    return c + removeDuplicateLetters(rest);
}

Linear for a fixed alphabet, but rebuilds a string on every level.

OptimalMonotonic Stack + Last Index

Time O(n)Space O(1)

Record each letter's last index. Scan once, skipping letters already in the stack. Before pushing c, pop every top that is larger and occurs again later — putting c earlier makes the string smaller and the popped letter can be re-added. Each letter is pushed/popped at most once per occurrence; the stack holds ≤ 26 chars.

Java

public String removeDuplicateLetters(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
    boolean[] inStack = new boolean[26];
    StringBuilder stack = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (inStack[c - 'a']) continue;
        while (stack.length() > 0) {
            char top = stack.charAt(stack.length() - 1);
            if (top < c || last[top - 'a'] < i) break; // smaller, or no later copy
            inStack[top - 'a'] = false;
            stack.deleteCharAt(stack.length() - 1);
        }
        stack.append(c);
        inStack[c - 'a'] = true;
    }
    return stack.toString();
}

Dry run"bcabc"

i index changed

i=0
b
i
c

a

b

c

push b → "b"
i=1
b

c
i
a

b

c

c > b, push → "bc"
i=2
b

c

a
i
b

c

pop c, b (seen later) → "a"
i=3
b

c

a

b
i
c

push b → "ab"
i=4
b

c

a

b

c
i
push c → "abc" ✔

One pass, constant extra space (alphabet-sized) — the expected answer.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Valid Subsequence	`O(2ⁿ·n)`	`O(n)`
Better	Greedy: Pick Smallest Safe First Letter	`O(k·n)`	`O(k·n)`
Optimal	Monotonic Stack + Last Index	`O(n)`	`O(1)`

Common pitfalls

Popping a larger top that never appears again — that letter is lost forever.
Forgetting the inStack skip — duplicates get pushed or pop valid letters.
Not clearing inStack on pop — the letter can never be re-added later.

Interview tips

State the greedy rule: drop a larger letter only if a later copy exists.
Argue O(n): each character is pushed and popped at most once.
Note the stack is bounded by 26, so extra space is O(1).

Pattern

Monotonic stack with removal budget → lexicographically smallest subsequence under constraints.

My notes saved in this browser