Remove Duplicate Letters

medium string stack greedy monotonic stack

Problem

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

Inputs = "cbacdcbc"

Output"acdb"

def remove_duplicate_letters(s):
    last = {c: i for i, c in enumerate(s)}
    stack, in_stack = [], set()
    for i, c in enumerate(s):
        if c in in_stack: continue
        while stack and c < stack[-1] and last[stack[-1]] > i:
            in_stack.discard(stack.pop())
        stack.append(c); in_stack.add(c)
    return "".join(stack)

function removeDuplicateLetters(s) {
  const last = {};
  for (let i = 0; i < s.length; i++) last[s[i]] = i;
  const stack = [], inStack = new Set();
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (inStack.has(c)) continue;
    while (stack.length && c < stack[stack.length - 1] && last[stack[stack.length - 1]] > i) {
      inStack.delete(stack.pop());
    }
    stack.push(c); inStack.add(c);
  }
  return stack.join("");
}

class Solution {
    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[] in = new boolean[26];
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (in[c - 'a']) continue;
            while (!stack.isEmpty() && c < stack.peek() && last[stack.peek() - 'a'] > i) {
                in[stack.pop() - 'a'] = false;
            }
            stack.push(c); in[c - 'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append(stack.pollLast());
        return sb.toString();
    }
}

string removeDuplicateLetters(string s) {
    int last[26] = {0};
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
    bool inStack[26] = {false};
    string stk;
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (inStack[c - 'a']) continue;
        while (!stk.empty() && c < stk.back() && last[stk.back() - 'a'] > i) {
            inStack[stk.back() - 'a'] = false;
            stk.pop_back();
        }
        stk.push_back(c); inStack[c - 'a'] = true;
    }
    return stk;
}

Explanation

We want each letter exactly once, arranged to be the smallest possible string. The greedy idea: build the answer on a stack, and whenever a smaller letter shows up, drop bigger letters already placed — but only if we can safely add them back later.

First we record last[c], the last index where each letter appears. We also keep an in_stack set so we never add a letter twice. Skipping a duplicate is free because it is already in our result.

For each new letter c not yet used: while the stack top is bigger than c and that top letter appears again later (last[top] > i), we pop it — putting c earlier makes the string smaller, and we know we can re-add the popped letter later. Then we push c.

The last[top] > i check is what keeps us safe: we only remove a letter if a future copy exists, so every required letter still ends up present exactly once.

Example: s = "cbacdcbc". The a pops the earlier c and b (both appear again later), and continuing the process yields the smallest valid arrangement "acdb".

Time: O(n) Space: O(1) (26 letters)