Skip to content

1081. Smallest Subsequence of Distinct Characters

SourceWeekly Contest 140 Q4DifficultyMediumRating2184

Description

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

 

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Solutions

Solution 1

Thinking

We need each distinct letter once, in the smallest subsequence that preserves order. \(n\le 1000\) fits a monotonic stack: a larger top that still appears later can be popped.

Record the last index of every letter. Skip a letter already on the stack; otherwise pop tops that are greater and still occur later, then push.

A set tracks membership. The stack order is the answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def smallestSubsequence(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        stk = []
        vis = set()
        for i, c in enumerate(s):
            if c in vis:
                continue
            while stk and stk[-1] > c and last[stk[-1]] > i:
                vis.remove(stk.pop())
            stk.append(c)
            vis.add(c)
        return "".join(stk)

 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 smallestSubsequence(String text) {
        int[] cnt = new int[26];
        for (char c : text.toCharArray()) {
            ++cnt[c - 'a'];
        }
        boolean[] vis = new boolean[26];
        char[] cs = new char[text.length()];
        int top = -1;
        for (char c : text.toCharArray()) {
            --cnt[c - 'a'];
            if (!vis[c - 'a']) {
                while (top >= 0 && c < cs[top] && cnt[cs[top] - 'a'] > 0) {
                    vis[cs[top--] - 'a'] = false;
                }
                cs[++top] = c;
                vis[c - 'a'] = true;
            }
        }
        return String.valueOf(cs, 0, top + 1);
    }
}

 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
class Solution {
public:
    string smallestSubsequence(string s) {
        int n = s.size();
        int last[26] = {0};
        for (int i = 0; i < n; ++i) {
            last[s[i] - 'a'] = i;
        }
        string ans;
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if ((mask >> (c - 'a')) & 1) {
                continue;
            }
            while (!ans.empty() && ans.back() > c && last[ans.back() - 'a'] > i) {
                mask ^= 1 << (ans.back() - 'a');
                ans.pop_back();
            }
            ans.push_back(c);
            mask |= 1 << (c - 'a');
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func smallestSubsequence(s string) string {
    last := make([]int, 26)
    for i, c := range s {
        last[c-'a'] = i
    }
    stk := []rune{}
    vis := make([]bool, 128)
    for i, c := range s {
        if vis[c] {
            continue
        }
        for len(stk) > 0 && stk[len(stk)-1] > c && last[stk[len(stk)-1]-'a'] > i {
            vis[stk[len(stk)-1]] = false
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, c)
        vis[c] = true
    }
    return string(stk)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function smallestSubsequence(s: string): string {
    const f = (c: string): number => c.charCodeAt(0) - 'a'.charCodeAt(0);
    const last: number[] = new Array(26).fill(0);
    for (const [i, c] of [...s].entries()) {
        last[f(c)] = i;
    }
    const stk: string[] = [];
    let mask = 0;
    for (const [i, c] of [...s].entries()) {
        const x = f(c);
        if ((mask >> x) & 1) {
            continue;
        }
        while (stk.length && stk[stk.length - 1] > c && last[f(stk[stk.length - 1])] > i) {
            mask ^= 1 << f(stk.pop()!);
        }
        stk.push(c);
        mask |= 1 << x;
    }
    return stk.join('');
}

Solution 2

Thinking

Solution 1 uses a hash set for membership. Twenty-six letters fit in a bit mask, flipped when a letter is pushed or popped.

Last-occurrence indices and the monotonic pops stay the same.

 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
class Solution {
    public String smallestSubsequence(String s) {
        int n = s.length();
        int[] last = new int[26];
        for (int i = 0; i < n; ++i) {
            last[s.charAt(i) - 'a'] = i;
        }
        Deque<Character> stk = new ArrayDeque<>();
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            if (((mask >> (c - 'a')) & 1) == 1) {
                continue;
            }
            while (!stk.isEmpty() && stk.peek() > c && last[stk.peek() - 'a'] > i) {
                mask ^= 1 << (stk.pop() - 'a');
            }
            stk.push(c);
            mask |= 1 << (c - 'a');
        }
        StringBuilder ans = new StringBuilder();
        for (char c : stk) {
            ans.append(c);
        }
        return ans.reverse().toString();
    }
}

Comments