Remove Duplicate Letters

Medium
359.

Remove Duplicate Letters

Remove Duplicate Letters is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Bloomberg interviews.

Given a string s, remove duplicate letters so that every letter appears exactly once, and among all such results return the lexicographically smallest one.

Example 1

Input
s = "bcabc"
Output
abc

Example 2

Input
s = "cbacdcbc"
Output
acdb

Example 3

Input
s = "abc"
Output
abc

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Duplicate Letters — Solution in Python, Java & C++

Remove Duplicate Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove Duplicate Letters is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Bloomberg interviews.

Problem statement

Given a string s, remove duplicate letters so that every letter appears exactly once, and among all such results return the lexicographically smallest one.

Example 1

Input: s = "bcabc"
Output: abc

Example 2

Input: s = "cbacdcbc"
Output: acdb

Example 3

Input: s = "abc"
Output: abc

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters.

Hints for Remove Duplicate Letters

  1. Hint 1

    Build the answer on a stack that you keep as small as possible, lexicographically.

  2. Hint 2

    Before pushing a character, pop any larger character on top — but only if that character occurs again later, so dropping it is safe.

  3. Hint 3

    Skip characters already on the stack; each letter must appear once.

How to solve Remove Duplicate Letters

Build the answer on a monotonic stack: before pushing a character, pop any larger top that still occurs later, and skip characters already on the stack.

Approach

  1. Record the last index of each character.
  2. For each ch: skip if already on the stack; while the top is greater than ch and its last index is beyond i, pop it; push ch.

Why it works

Popping a larger character that reappears later never loses it and makes the prefix smaller; refusing to pop one that does not reappear preserves the every-letter-once guarantee. The stack is therefore the lexicographically smallest valid subsequence.

Complexity

  • Time — O(n)
  • Space — O(26)

Pitfalls

  • Forgetting the "occurs later" check drops letters permanently.

Reference solution

Python

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

Java

public static String removeDuplicateLetters(String s) {
    int[] last = new int[26];
    for (int i = 0; i < 26; i++) last[i] = -1;
    for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
    StringBuilder stack = new StringBuilder();
    boolean[] inStack = new boolean[26];
    for (int i = 0; i < s.length(); i++) {
        int c = s.charAt(i) - 'a';
        if (inStack[c]) continue;
        while (stack.length() > 0) {
            int top = stack.charAt(stack.length() - 1) - 'a';
            if (top > c && last[top] > i) {
                inStack[top] = false;
                stack.deleteCharAt(stack.length() - 1);
            } else {
                break;
            }
        }
        stack.append(s.charAt(i));
        inStack[c] = true;
    }
    return stack.toString();
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms