# 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.

Constraints:

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

## Examples

``````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.

## Solution

``````class RemoveDuplicateLetters {
public:
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';
counter[idx]--;
if (seen[idx]) { continue; }
while (!ss.empty() && ss.top() > c && counter[ss.top() - 'a'] > 0) {
seen[ss.top() - 'a'] = false;
ss.pop();
}
if (!seen[idx]) {
ss.push(c);
seen[idx] = true;
}
}
string result = "";
while (!ss.empty()) {
result = ss.top() + result;
ss.pop();
}
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:
continue
while stack and stack[-1] > c and counter[stack[-1]] > 0:
seen.remove(stack.pop())
if c not in seen:
stack.append(c)
``````
• Time: `O(n^2)`
• Space: `O(1)` – counter, seen, and stack will have the size at most 26. constant