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.

解答

• 方法一

先利用 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