去除重复字母

[louzhedong]

习题

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1：

输入：s = "bcabc"
输出："abc"
示例 2：

输入：s = "cbacdcbc"
输出："acdb"

提示：

1 <= s.length <= 104
s 由小写英文字母组成

思路

1. 创建一个map统计s中每个字母出现的次数
2. 创建一个栈维护字典序最小的字符串序列
3. 遍历字符串，出现的字符map统计-1
4. 如果当前字符未在栈中，则需要将当前字符推入栈
5. 在推入栈时，需要判断栈顶的元素的字典序是否比当前字符大，如果大于当前字符且s中还存在另外的栈顶元素，则将该元素pop

解答

javascript

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
   var map = new Map(), stack = [];
   for(var i = 0, length = s.length; i < length; i++) {
       var current = s[i];
       if (map.get(current)) {
           map.set(current, map.get(current) + 1);
       } else {
           map.set(current, 1);
       }
   }

    for (var i = 0, length = s.length; i < length; i++) {
        var current = s[i];
        map.set(current, map.get(current) - 1);
        if (stack.includes(current) == false) {
            var j = stack.length;
            while(j-- && stack[j] > current && map.get(stack[j])) {
                stack.pop();
            }
            stack.push(current);
        }
    }
    return stack.join('');
};