# 316. Remove Duplicate Letters

### Leetcode

<https://leetcode.com/problems/remove-duplicate-letters/>

### 題目

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.

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

先利用 hash table 紀錄各字母總共出現幾次，再遍歷一次字串，用 visited 紀錄此字母是否被訪問過

```
var removeDuplicateLetters = function(s) {
    const hash = {};
    for(let i=0; i<s.length; i++) {
        const val = s[i];
        if(!hash[val]) hash[val] = 1;
        else hash[val]++;
    }
    
    // default 先把結果字串第一個放 0 (因為 charcode 小於所有英文字母)
    let res = '0';
    const visited = {};
    for(let i=0; i<s.length; i++) {
        const val = s[i];
        hash[val]--;
        // 如果訪問過的話遍歷下一個字母
        if(visited[val]) continue;

        let last = res[res.length-1];
        // 只要目前字母大於 res 最後一個字母，且 hash table 裡還有最後一個字母
        while(val<last && hash[last]) {
            // 去掉最後一個字母
            res = res.substring(0, res.length-1);
            visited[last] = false;
            last = res[res.length-1];
        }
        res += val;
        visited[val] = true;
    }
    
    // 把 0 去掉
    return res.substring(1);
};
```

Runtime: 117 ms, faster than 30.77% of JavaScript online submissions for Remove Duplicate Letters.

Memory Usage: 40.2 MB, less than 93.59% of JavaScript online submissions for Remove Duplicate Letters.

### 測資

```
console.log(removeDuplicateLetters("cbacdcbc"))
```

### 參考資料

<https://www.cnblogs.com/grandyang/p/5085379.html>
