LeetCode 316. Remove Duplicate Letters

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String removeDuplicateLetters(String s) {
        boolean[] seen = new boolean[26];
        int[] num = new int[26];
        char[] cs = s.toCharArray();
        for (char c : cs)
            num[c - 'a']++;
        StringBuilder ans = new StringBuilder();
        for (char c : cs) {
            if (!seen[c - 'a']) {
                while (ans.length() > 0 && ans.charAt(ans.length() - 1) > c && num[ans.charAt(ans.length() - 1) - 'a'] > 0) {
                    seen[ans.charAt(ans.length() - 1) - 'a'] = false;
                    ans.deleteCharAt(ans.length() - 1);
                }
                seen[c - 'a'] = true;
                ans.append(c);
            }
            num[c - 'a']--;
        }
        return ans.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<bool> seen(26);
        vector<int> num(26);
        for (char c : s)
            ++num[c - 'a'];
        string stk;
        for (char c : s) {
            if (!seen[c - 'a']) {
                while (!stk.empty() && stk.back() > c && num[stk.back() - 'a'] > 0) {
                    seen[stk.back() - 'a'] = false;
                    stk.pop_back();
                }
                seen[c - 'a'] = true;
                stk.push_back(c);
            }
            --num[c - 'a'];
        }
        return stk;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = []
        remain_counter = collections.Counter(s)
        seen = set()

        for c in s:
            if c not in seen:
                while stack and stack[-1] > c and remain_counter[stack[-1]] > 0:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
            remain_counter[c] -= 1
        return ''.join(stack)