Remove Duplicate Letters

Description

Given a string which contains only lowercase letters, 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.

Example 1:

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Solution(javascript)

/*
 * @lc app=leetcode id=316 lang=javascript
 *
 * [316] Remove Duplicate Letters
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
const removeDuplicateLetters = function (s) {
  const map = {}
  const used = {}
  const stack = []
  for (const c of s) {
    map[c] = (map[c] || 0) + 1
  }
  for (const c of s) {
    while (
      c <= stack[stack.length - 1]
      && map[stack[stack.length - 1]] > 1
      && !used[c]
    ) {
      const last = stack.pop()
      used[last] = false
      map[last] -= 1
    }
    if (!used[c]) {
      stack.push(c)
      used[c] = true
    } else {
      map[c] -= 1
    }
  }
  return stack.join('')
}
// @lc code=end

// console.log(
//   removeDuplicateLetters(
//     // 'cbacdcbc',
//     'bbcaac', // bac
//     // 'abacb', // abc
//   ),
// )