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 (Javascript)

/**
 * @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);
};

Solution (Java)

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] charCount = new int[26];
        boolean[] charAdded = new boolean[26];
        // Build the char count array
        for (char c : s.toCharArray()) {
            charCount[c - 'a'] += 1;
        }
        StringBuilder sb = new StringBuilder();
        // i = index of the input string
        // j = index of the output stringBuilder
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            // If the curr char is NOT already added in the final string
            if (!charAdded[curr - 'a']) {
                // If the prev char in final string is lexicographically greater than curr char of
                // input string
                // And there are more characters in charCount array then we can remove this prev
                // char from final string
                // Do this check iteratively until all characters are removed from the final string
                // or prev char < curr char
                while (j > 0 && sb.charAt(j - 1) > curr && charCount[sb.charAt(j - 1) - 'a'] > 0) {
                    charAdded[sb.charAt(j - 1) - 'a'] = false;
                    sb.deleteCharAt(j - 1);
                    j--;
                }
                // Add the curr char in final string and mark that character as added in the string
                sb.append(curr);
                charAdded[curr - 'a'] = true;
                j++;
            }
            // Reduce the count of the current character from the charCount array
            charCount[curr - 'a'] -= 1;
        }
        return sb.toString();
    }
}

Explain:

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

Complexity:

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