Smallest Subsequence of Distinct Characters

Problem

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

Examples

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/

Solution

Method 1 – Monotonic Stack (Greedy)

Intuition

To get the lexicographically smallest subsequence with all distinct characters, we use a stack to build the answer. We greedily remove characters from the stack if a smaller character is available later and hasn't been used yet.

Approach

1. Count the last occurrence of each character in the string.
2. Use a stack to build the answer and a set to track used characters.
3. For each character:
   • If already used, skip.
   • While the stack is not empty and the top character is greater than the current and appears later, pop it from the stack and mark as unused.
   • Push the current character and mark as used.
4. Join the stack to get the answer.

Code

C++

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;
    }
};

Go

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)
}

Java

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();
    }
}

Kotlin

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()
    }
}

Python

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)

Rust

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()
    }
}

TypeScript

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("");
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of s. Each character is pushed and popped at most once.
• 🧺 Space complexity: O(1), since the alphabet size is constant (26).