[1081] 不同字符的最小子序列

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。

示例 1：

输入："cdadabcc"

输出："adbc"

示例 2：

输入："abcd"

输出："abcd"

示例 3：

输入："ecbacba"

输出："eacb"

示例 4：

输入："leetcode"

输出："letcod"

提示：

1 <= text.length <= 1000

text 由小写英文字母组成

注意：本题目与 [316] 去除重复字母 相同

这题算是集所有技巧于大成的去重题了，里面用到了许多的技巧。

首先审题，题目要求有三：

1. 对字符串去重
2. 不能打乱原有字符串的相对位置
3. 保证返回的字典序最小

先一步一步来看，条件二要求我们不能对原有字符串数组进行排序，这样我们最常用的数组去重方式（排序后使用快慢指针去重）就不能被使用了。

因此我们只能使用hashMap的方式来记录下出现过的元素，从而比对进行去重。

那么怎样保证条件三：最终的字典序最小呢？这个就是题目的难点了。

在插入一个字符的时候我们必须保证该字符之前的字符在字典序上要比当前字符小，不满足要求的需要被剔除，因此我们可以使用栈的方式来实现这个目的。当遇到栈顶元素字典序大于当前元素，则不断执行出栈操作，直到符合字典序为止。

那么这样做又引入了一个新的问题，当一个元素之后都不会再出现了，却因为在比较中字典序较大而被出栈了，那么我们就会永远的丢失这个元素，从而让结果有误。

因此我们还需要一个计数器，在比较字典序出栈之前判断之后是否还会有该元素，若没有则不能出栈该元素。（这里用指针循环去判断后面还有没有该元素在时间复杂度上就差了，用空间换下时间）。

之后我们只需要将栈中元素转换为数组即可完成题目要求。

var removeDuplicateLetters = function(s) {
  const stack = [];
  // 用于去重的 hashMap
  const hasChMap = {};

  // 每个字母出现次数计数器
  const chCountMap = {};

  for (let ch of s) {
    if (!chCountMap[ch]) {
      chCountMap[ch] = 0;
    }
    chCountMap[ch]++;
    hasChMap[ch] = false;
  }

  for (let ch of s) {
    // 该字母剩余出现次数-1
    chCountMap[ch]--;

    if (!hasChMap[ch]) {
      // 比较与栈顶字母的字典序，直到栈顶字母序比当前字母小为止
      while (stack.length > 0 && stack[stack.length - 1] > ch) {
        // 如果该栈顶字母之后没有出现次数了，则停止出栈操作
        if (chCountMap[stack[stack.length - 1]] === 0) break;
        const popCh = stack.pop();
        hasChMap[popCh] = false;
      }
      hasChMap[ch] = true;
      stack.push(ch);
    }
  }
  return stack.join('');
};