Blind Plus 100 Visualized

#82 · Stack

Remove Duplicate Letters

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

MediumLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Monotonic stack of letters

A stack that tends to increase from bottom to top. A new letter pops bigger letters from the top, but only those that still appear later in the string, since popping a letter that never returns would lose it.

Memory layout

At most 26 characters on the stack (one per distinct lowercase letter).

OperationCost
push / popO(1)
totalO(n)

Last-occurrence table

last[ch] is the final index where ch occurs. A letter on the stack can be popped at position i only if last[ch] > i.

Memory layout

A fixed 26-slot array (or a small map).

OperationCost
buildO(n)
lookupO(1)

In-stack set (bitmask)

Records which letters are already in the stack so duplicates are skipped. For 26 lowercase letters one 32-bit integer does the job.

Memory layout

One integer; bit k set means letter k is on the stack.

OperationCost
test / set / clearO(1)

Why it fits

  • Lexicographic minimality wants smaller letters as early as possible, which is exactly what popping bigger earlier letters achieves.
  • The last-occurrence table makes pops safe: a bigger letter is removed only if another copy comes later, so the result still contains every distinct letter.
  • Skipping a letter already on the stack is right: the earlier copy is in a better position than a later one for a smallest result.

Why alternatives degrade

Sorting the distinct letters:
It ignores the relative order of the original string; the answer must be a subsequence.
Greedy removal of the first duplicate:
Which copy to keep depends on the letters that follow; local choices fail ("bcabc" needs the later b).
Trying all subsets:
Exponential in the number of repeated letters.

Four approaches, from naive to production

1 · beginner

Try every choice of occurrences

time O(k^d · d log d)space O(d)

For each distinct letter choose exactly one of its occurrences; build the string from the chosen positions in order and keep the smallest result.

string removeDuplicateLetters(string s) {
    string letters;
    for (char ch : s) if (letters.find(ch) == string::npos) letters += ch;
    vector<vector<int>> positions(letters.size());
    for (int i = 0; i < (int)s.size(); i++) positions[letters.find(s[i])].push_back(i);
    string best = "";
    vector<int> chosen;
    function<void(int)> pick = [&](int k) {
        if (k == (int)letters.size()) {
            vector<int> sorted(chosen); sort(sorted.begin(), sorted.end());
            string candidate; for (int i : sorted) candidate += s[i];
            if (best.empty() || candidate < best) best = candidate;
            return;
        }
        for (int p : positions[k]) {
            chosen.push_back(p);
            pick(k + 1);
            chosen.pop_back();
        }
    };
    pick(0);
    return best;
}

Flaws & bottlenecks

  • Exponential in the number of repeated letters (k occurrences per letter, d distinct letters).
  • Builds and compares many candidate strings.
  • Unusable once letters repeat many times (a 10⁴ long string).

Interviewer cross-questions

Why is every valid answer one occurrence per letter?

Say: The answer contains each distinct letter exactly once, taken in the original order, so it is determined by which occurrence of each letter is used.

How large can the search get?

Say: The product of occurrence counts: with 26 letters repeated 400 times each it is 400²⁶.

What does the greedy approach exploit?

Say: The first letter of the best answer is the smallest letter that still leaves every other letter available in the suffix.

2 · intermediate

Greedy recursion on the smallest feasible letter

time O(26 · n)space O(n) (recursion and copies)

Scan from the left, counting down letters. Stop when some letter would have no copy left; among the scanned characters pick the smallest as the next answer letter, remove all its copies from the suffix and recurse.

string removeDuplicateLetters(string s) {
    if (s.empty()) return "";
    map<char, int> count;
    for (char ch : s) count[ch]++;
    int pos = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] < s[pos]) pos = i;
        count[s[i]]--;
        if (count[s[i]] == 0) break;
    }
    string rest;
    for (int i = pos + 1; i < (int)s.size(); i++) if (s[i] != s[pos]) rest += s[i];
    return string(1, s[pos]) + removeDuplicateLetters(rest);
}

Flaws & bottlenecks

  • Builds a new string at every level (slice / split / join).
  • Recursion depth up to 26 and repeated counting.
  • Harder to reason about than the stack idea.

Interviewer cross-questions

Why stop at the first letter whose count hits zero?

Say: That letter cannot be postponed any further: if we skipped it we would lose it. So the next answer letter must come from the prefix up to and including it.

Why pick the leftmost smallest letter?

Say: If the smallest letter occurs several times in the prefix, the leftmost choice leaves the most characters for the rest.

Can recursion be removed?

Say: Yes: a monotonic stack does the same job in one pass.

3 · advanced

Monotonic stack with last occurrences

time O(n)space O(1) (at most 26 letters)

Record each letter's last index. Scan left to right; skip letters already on the stack; pop bigger letters on top that occur again later; push the current letter.

string removeDuplicateLetters(string s) {
    unordered_map<char, int> last;
    for (int i = 0; i < (int)s.size(); i++) last[s[i]] = i;
    string stack;
    unordered_set<char> inStack;
    for (int i = 0; i < (int)s.size(); i++) {
        char ch = s[i];
        if (inStack.count(ch)) continue;
        while (!stack.empty() && stack.back() > ch && last[stack.back()] > i) {
            inStack.erase(stack.back()); stack.pop_back();
        }
        stack.push_back(ch);
        inStack.insert(ch);
    }
    return stack;
}

Flaws & bottlenecks

  • Needs the last-occurrence table (a pre-pass).
  • Easy to forget the in-stack check, which produces duplicates.
  • Uses hash containers where fixed 26-slot arrays would be faster.

Interviewer cross-questions

Why check last[top] > i before popping?

Say: If the top letter never occurs again, popping it would drop it from the result.

Why skip a letter already on the stack?

Say: Its earlier copy is already in the best position: placing a later copy could only make the string larger or equal.

Is this the same pattern as Remove K Digits?

Say: Yes: both pop larger values from a stack to make the string smaller, with a different rule for when popping is allowed.

4 · expert

Fixed arrays and a bitmask

time O(n)space O(1)

Map letters to 0 … 25. Use a 26-slot array for last occurrences and one integer bitmask for the in-stack set, so no hashing is involved.

string removeDuplicateLetters(string s) {
    int last[26]; fill(last, last + 26, -1);
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
    vector<int> stack;
    int inStack = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        int c = s[i] - 'a';
        if ((inStack >> c) & 1) continue;
        while (!stack.empty() && stack.back() > c && last[stack.back()] > i) {
            inStack &= ~(1 << stack.back()); stack.pop_back();
        }
        stack.push_back(c);
        inStack |= 1 << c;
    }
    string result;
    for (int c : stack) result += (char)('a' + c);
    return result;
}

Flaws & bottlenecks

  • Assumes lowercase letters; other alphabets need a wider mask or a map.
  • Bit tricks hurt readability.
  • Stack of ints must be converted back to characters.

Interviewer cross-questions

What if the input includes uppercase or Unicode characters?

Say: Use a bigger table (128 or 256 slots) with a boolean array, or a hash map for arbitrary Unicode.

Why a bitmask?

Say: Membership tests, insertion and removal become single-instruction operations on a register.

What are the edge cases?

Say: Empty string, a single letter, all distinct letters (unchanged), all the same letter (one letter), and already sorted input.

Synchronized code walkthrough

Showing: Try every choice of occurrences — shares the player above; click any step to jump.

string removeDuplicateLetters(string s) {
    string letters;
    for (char ch : s) if (letters.find(ch) == string::npos) letters += ch;
    vector<vector<int>> positions(letters.size());
    for (int i = 0; i < (int)s.size(); i++) positions[letters.find(s[i])].push_back(i);
    string best = "";
    vector<int> chosen;
    function<void(int)> pick = [&](int k) {
        if (k == (int)letters.size()) {
            vector<int> sorted(chosen); sort(sorted.begin(), sorted.end());
            string candidate; for (int i : sorted) candidate += s[i];
            if (best.empty() || candidate < best) best = candidate;
            return;
        }
        for (int p : positions[k]) {
            chosen.push_back(p);
            pick(k + 1);
            chosen.pop_back();
        }
    };
    pick(0);
    return best;
}