316. Remove Duplicate Letters

Problem

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear 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"

Solution

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
  var count = {};
  var len = s.length;
  var index = 0;

  if (!len) return '';

  for (var i = 0; i < len; i++) {
    if (count[s[i]] === undefined) count[s[i]] = 0;
    count[s[i]]++;
  }

  for (var j = 0; j < len; j++) {
    if (s[j] < s[index]) index = j;
    if (--count[s[j]] === 0) break;
  }

  var firstChar = s[index];
  var restString = s.substr(index + 1);

  restString = restString.replace(new RegExp(firstChar, 'g'), '');

  return firstChar + removeDuplicateLetters(restString);
};

Explain:

贪心，每次找到排第一的字符，再递归。

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).