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.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Example 1:

```Input: s = "bcabc"
Output: "abc"
```

Example 2:

```Input: s = "cbacdcbc"
Output: "acdb"
```

Constraints:

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

Idea:

Hash + Stack

Solution:

``````/**
* @param {string} s
* @return {string}
*/
var removeDuplicateLetters = function(s) {
let chars = s.split('');
// record the index of last occurrence for each character
let lastIndex = new Map();
for (let i = 0; i < chars.length; i++) {
lastIndex.set(chars[i], i);
}
let stack = [];
let used = new Map();
for (let i = 0; i < chars.length; i++) {
// if the current character has been used, skip it
if (used.has(chars[i]) && used.get(chars[i])) continue;

// if the current character is smaller than stack[stack.length - 1]
// and the last index of stack[stack.length - 1] is larger than i, it means we can use it later,
// so we pop it out and mark used as false
while (stack.length !== 0 && chars[i] < stack[stack.length - 1] && lastIndex.get(stack[stack.length - 1]) > i)
used.set(stack.pop(), false);

stack.push(chars[i]);
used.set(chars[i], true);
}
let ans = [];
while (stack.length !== 0) ans.push(stack.pop());
return ans.reverse().join('');
};``````