316. Remove Duplicate Letters

316. Remove Duplicate Letters (Medium)

Given a string s, 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: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

 

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

Companies:
Facebook, Apple, Microsoft

Related Topics:
String, Stack, Greedy, Monotonic Stack

Similar Questions:

• Smallest K-Length Subsequence With Occurrences of a Letter (Hard)

Solution 1. Greedy + Recursion

Which character can be placed at the first index?

The characters that have all the unique characters to their right (including themselves). We pick the smallest one from this set.

For example, s = "cbca", character b and c has all abc to its right, but a only have a to its right. So we must pick the smallest from bc, i.e. b.

If we scan from left to right, we need to stop the search when the count of the current character drops to 0 because that's when we have one less unique character (the current one) to the right.

We pick the smallest character when we stop the search at put it at the beginning.

Assume the index of this smallest character is i, then we should continue our greedy search from i + 1.

Consider the following input whose result is "bcda".

2 2 1 1 0 0 0 0
c b c b d a b c
  ^ ^   ^ ^        <- selected characters

The number above each letter is the count of the same letters to its right.

We traverse from left to right:

1. For s[0]=c, it's the smallest so far, so best = 0.
2. For s[1]=b, it's the smallest so far, so best = 1.
3. For s[2]=c, it's not the smallest, skip.
4. For s[3]=b, it's the same as s[best], skip.
5. For s[4]=d, the count of d is 0 so we must stop our greedy search here and pick best = 1, s[best] = b.
6. Then we continue our greedy search from best + 1 = 2.

// OJ: https://leetcode.com/problems/remove-duplicate-letters/
// Author: github.com/lzl124631x
// Time: O(NC) where `N` is the length of `s`, and `C` is the range of the letters
// Space: O(NC)
class Solution {
public:
    string removeDuplicateLetters(string s) {
        if (s.empty()) return s;
        int cnt[26] = {};
        for (char c : s) cnt[c - 'a']++;
        int best = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] < s[best]) best = i;
            if (--cnt[s[i] - 'a'] == 0) break;
        }
        string t = s.substr(best + 1);
        t.erase(remove(t.begin(), t.end(), s[best]), t.end());
        return s[best] + removeDuplicateLetters(t);
    }
};

Solution 2. Greedy

Same idea as Solution 1, use iterative method instead of recursive.

// OJ: https://leetcode.com/problems/remove-duplicate-letters/
// Author: github.com/lzl124631x
// Time: O(NC) where `N` is the length of `s`, and `C` is the range of the letters
// Space: O(N + C)
class Solution {
public:
    string removeDuplicateLetters(string s) {
        if (s.empty()) return s;
        int N = s.size(), cnt[26] = {}, added[26] = {}, unique = 0;
        vector<int> rightCnt(N); // `rightCnt[i]` is the count of `s[i]` to the right of `s[i]`
        string ans;
        for (int i = N - 1; i >= 0; --i) {
            unique += cnt[s[i] - 'a'] == 0; // `unique` is the count of unique characters in `s`
            rightCnt[i] = cnt[s[i] - 'a']++;
        }
        for (int i = 0; i < N && ans.size() < unique;) {
            int best = -1;
            for (; i < N; ++i) {
                if (added[s[i] - 'a']) continue;
                if (best == -1 || s[i] < s[best]) best = i;
                if (!rightCnt[i]) break;
            }
            ans += s[best];
            added[s[best] - 'a'] = 1;
            i = best + 1;
        }
        return ans;
    }
};

Solution 3. Monotonic stack + Greedy

We only keep a monotonic increasing sequence.

One key is that, when we scan to s[i], if s[i] has been used, we should skip it because if s[i] can be selected earlier and now, selecting it now is no better than selecting it earlier.

// OJ: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
// Author: github.com/lzl124631x
// Time: O(N) where `N` is the length of `s`, and `C` is the range of the letters
// Space: O(C)
class Solution {
public:
    string smallestSubsequence(string s) {
        int last[26] = {}, used[26] = {}, N = s.size();
        for (int i = 0; i < N; ++i) last[s[i] - 'a'] = i;
        string ans;
        for (int i = 0; i < N; ++i) {
            if (used[s[i] - 'a']) continue; // once used, don't use it again.
            while (ans.size() && ans.back() > s[i] && i < last[ans.back() - 'a']) { // If the stack top `x` is greater than the current letter, and there are more letters `x` available, we pop `x`
                used[ans.back() - 'a'] = 0;
                ans.pop_back();
            }
            ans.push_back(s[i]);
            used[s[i] - 'a'] = 1;
        }
        return ans;
    }
};