Smallest Subsequence of Distinct Characters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    string smallestSubsequence(string s) {
        vector<int> last(26);
        for (int i = 0; i < s.size(); ++i) last[s[i]-'a'] = i;
        vector<bool> used(26);
        string ans;
        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (used[c-'a']) continue;
            while (!ans.empty() && ans.back() > c && last[ans.back()-'a'] > i) {
                used[ans.back()-'a'] = false;
                ans.pop_back();
            }
            ans.push_back(c);
            used[c-'a'] = true;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func smallestSubsequence(s string) string {
    last := make([]int, 26)
    for i, c := range s { last[c-'a'] = i }
    used := make([]bool, 26)
    ans := []byte{}
    for i := 0; i < len(s); i++ {
        c := s[i]
        if used[c-'a'] { continue }
        for len(ans) > 0 && ans[len(ans)-1] > c && last[ans[len(ans)-1]-'a'] > i {
            used[ans[len(ans)-1]-'a'] = false
            ans = ans[:len(ans)-1]
        }
        ans = append(ans, c)
        used[c-'a'] = true
    }
    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public String smallestSubsequence(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); ++i) last[s.charAt(i)-'a'] = i;
        boolean[] used = new boolean[26];
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (used[c-'a']) continue;
            while (ans.length() > 0 && ans.charAt(ans.length()-1) > c && last[ans.charAt(ans.length()-1)-'a'] > i) {
                used[ans.charAt(ans.length()-1)-'a'] = false;
                ans.deleteCharAt(ans.length()-1);
            }
            ans.append(c);
            used[c-'a'] = true;
        }
        return ans.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun smallestSubsequence(s: String): String {
        val last = IntArray(26)
        for (i in s.indices) last[s[i]-'a'] = i
        val used = BooleanArray(26)
        val ans = StringBuilder()
        for (i in s.indices) {
            val c = s[i]
            if (used[c-'a']) continue
            while (ans.isNotEmpty() && ans.last() > c && last[ans.last()-'a'] > i) {
                used[ans.last()-'a'] = false
                ans.deleteAt(ans.length-1)
            }
            ans.append(c)
            used[c-'a'] = true
        }
        return ans.toString()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        used = set()
        ans = []
        for i, c in enumerate(s):
            if c in used: continue
            while ans and ans[-1] > c and last[ans[-1]] > i:
                used.remove(ans.pop())
            ans.append(c)
            used.add(c)
        return ''.join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn smallest_subsequence(s: String) -> String {
        let s = s.as_bytes();
        let mut last = [0; 26];
        for (i, &c) in s.iter().enumerate() { last[(c-b'a') as usize] = i; }
        let mut used = [false; 26];
        let mut ans = Vec::new();
        for (i, &c) in s.iter().enumerate() {
            let idx = (c-b'a') as usize;
            if used[idx] { continue; }
            while let Some(&top) = ans.last() {
                let tidx = (top-b'a') as usize;
                if top > c && last[tidx] > i {
                    used[tidx] = false;
                    ans.pop();
                } else { break; }
            }
            ans.push(c);
            used[idx] = true;
        }
        String::from_utf8(ans).unwrap()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    smallestSubsequence(s: string): string {
        const last: Record<string, number> = {};
        for (let i = 0; i < s.length; ++i) last[s[i]] = i;
        const used = new Set<string>();
        const ans: string[] = [];
        for (let i = 0; i < s.length; ++i) {
            const c = s[i];
            if (used.has(c)) continue;
            while (ans.length && ans[ans.length-1] > c && last[ans[ans.length-1]] > i) {
                used.delete(ans.pop()!);
            }
            ans.push(c);
            used.add(c);
        }
        return ans.join("");
    }
}