BFE.devAI解答 - JavaScript 代码题
112. 重複の文字を削除する

解题思路：

题目要求去掉字符串中重复的字符，且返回字典序最小的字符串。因此，可以使用贪心算法，从最小的字符开始，依次在字符串中查找这个字符，并且保证后面的字符一定比前面的字符要“小”。

同时，为了保证字典序最小，需要满足在找到下一个字符之前，先判断当前字符串是否符合要求。如果符合要求，则直接返回，否则继续找下一个字符。

具体步骤如下：

1. 构建一个桶，记录每个字符出现的次数。
2. 遍历字符串，对于每个字符，先检查桶中该字符的出现次数是否为0。如果为0，则跳过该字符；否则，将该字符加入当前结果字符串中。
3. 对于加入结果字符串中的字符，将其桶中的出现次数减1。
4. 检查当前结果字符串是否符合要求。即，是否还存在其他字符比该字符小且未加入结果字符串中。如果存在，继续找下一个字符；否则，停止查找，直接返回结果字符串。

根据贪心算法的思路，可以使用一个指针来记录当前结果字符串中最后一个字符的位置，以判断后面的字符是否合法。

JavaScript 代码实现如下：

function removeDuplicate(str) {
  const bucket = new Array(26).fill(0); // 构建桶
  const n = str.length;
  let p = -1; // 当前结果字符串中最后一个字符的位置
  let res = ''; // 结果字符串

  for (let i = 0; i < n; i++) {
    const c = str.charAt(i);
    const idx = c.charCodeAt() - 'a'.charCodeAt(); // 计算字符对应的桶的索引
    if (bucket[idx] === 0) continue; // 如果该字符的出现次数为0，跳过该字符

    let k = p; // 初始化指针
    while (k >= 0 && res.charAt(k) > c) { // 查找合法字符
      const prevIdx = res.charAt(k).charCodeAt() - 'a'.charCodeAt();
      if (bucket[prevIdx] === 0) break; // 如果后面的字符中已经没有比该字符小的了，则停止查找
      k--; // 指针左移
    }
    if (k >= 0 && res.charAt(k) >= c) { // 如果存在合法字符，则直接返回结果字符串
      bucket[idx]--; // 桶中该字符的出现次数减1
      continue;
    }

    // 如果不存在合法字符，则将该字符加入结果字符串
    while (p >= 0 && res.charAt(p) > c && bucket[res.charAt(p).charCodeAt() - 'a'.charCodeAt()] > 0) {
      p--; // 将不符合要求的字符从结果字符串中删除
    }
    res = res.substring(0, p + 1) + c; // 将该字符加入结果字符串
    p++; // 指针右移
    bucket[idx]--; // 桶中该字符的出现次数减1
  }

  return res;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$