Remove Duplicate Letters

Published: Jan 23, 2023

Medium Monotonic Stack Greedy String

Problem Description

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.


  • 1 <= s.length <= 10**4
  • s consists of lowercase English letters.


Example 1
Input: s = "bcabc"
Output: "abc"
Example 2
Input: s = "cbacdcbc"
Output: "acdb"
Example 3
Input: s = "bbcaac
Output: "bac"

How to Solve

Creating a monotonic increasing stack is a good approach for this problem. Since the indices of characters matter, simply sort and eliminate duplicates is not the answer.

If a current character is less than the last character in a stack, only when the last character appears in the later index, the last character is popped out from the stack. Once a character is put in the stack, the same character should not be added. It is checked using seen vector (C++) or set (Python).

In the end, create the answer by concatenating the characters in stack.


class RemoveDuplicateLetters {
    string removeDuplicateLetters(string s) {
        vector<int> counter(26, 0);
        for (char &c : s) { counter[c - 'a']++; }
        vector<bool> seen(26, false);
        stack<char> ss;
        for (char &c : s) {
            int idx = c - 'a';
            if (seen[idx]) { continue; }
            while (!ss.empty() && > c && counter[ - 'a'] > 0) {
                seen[ - 'a'] = false;
            if (!seen[idx]) {
                seen[idx] = true;
        string result = "";
        while (!ss.empty()) {
            result = + result;
        return result;

class RemoveDuplicateLetters:
    def removeDuplicateLetters(self, s: str) -> str:
        counter = collections.Counter(s)
        seen, stack = set(), []
        for c in s:
            counter[c] -= 1
            if c in seen:
            while stack and stack[-1] > c and counter[stack[-1]] > 0:
            if c not in seen:
        return ''.join(stack)


  • Time: O(n^2)
  • Space: O(1) – counter, seen, and stack will have the size at most 26. constant