Skip to content

Remove Duplicate Letters⚓︎

Link

Description⚓︎

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.

A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one.

Example 1:

  • Input: s = "bcabc"
  • Output: "abc"

Example 2:

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

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of lowercase English letters.

Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    string removeDuplicateLetters(string s) {
        const int MAXN = 26;
        vector<int> cnts(MAXN, 0);
        vector<bool> enter(MAXN, false);
        stack<char> stk;

        for (char ch : s) {
            cnts[ch - 'a']++;
        }

        for (char ch : s) {
            if (!enter[ch - 'a']) {
                while (!stk.empty() && stk.top() > ch && cnts[stk.top() - 'a'] > 0) {
                    enter[stk.top() - 'a'] = false;
                    stk.pop();
                }
                stk.push(ch);
                enter[ch - 'a'] = true;
            }
            cnts[ch - 'a']--;
        }

        string res = "";
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }

        reverse(res.begin(), res.end());
        return res;
    }
};

Better way of writing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string removeDuplicateLetters(string s) {
        string stk;
        unordered_map<char, bool> enter;
        unordered_map<char, int> last;

        for (int i = 0; i < s.size(); i++) {
            last[s[i]] = i;
        }

        for (int i = 0; i < s.size(); i++) {
            if (enter[s[i]]) continue;

            while (!stk.empty() && stk.back() > s[i] && last[stk.back()] > i) {
                enter[stk.back()] = false;
                stk.pop_back();
            }

            stk += s[i];
            enter[s[i]] = true;
        }

        return stk;
    }
};
  • Time complexity: \(O(n)\);
  • (Extra) space complexity: \(O(1)\).