316. Remove Duplicate Letters

Posted on Edited on In

316. Remove Duplicate Letters

Description

Difficulty: Medium

Related Topics: String, Stack, Greedy, Monotonic Stack

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:

1
2
Input: s = "bcabc"
Output: "abc"

Example 2:

1
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/

Hints/Notes

  • With stack and set we can get the substring with no duplicate, but not necessarily the smallest
  • Add a counter to count the frequency of letters, then we can pop the letters without worrying there’s no more

Solution

Language: C++

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
35
36
37
38
39
40
class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> count(26, 0);
        vector<bool> inStack(26, false);
        stack<char> stk;
        for (char c : s) {
            count[c - 'a']++;
        }
        
        for (char c : s) {
            int idx = c - 'a';
            count[idx]--;
            
            if (inStack[idx]) {
                continue;
            }

            while (!stk.empty() && stk.top() > c) {
                char top = stk.top();
                if (count[top - 'a'] == 0) {
                    break;
                }
                inStack[top - 'a'] = false;
                stk.pop();
            }

            stk.push(c);
            inStack[c - 'a'] = true;
        }

        string res;
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};