LeetCode Entry

1081. Smallest Subsequence of Distinct Characters

19.07.2026 medium 2026 kotlin rust

Smallest uniq-chars subsequence

1081. Smallest Subsequence of Distinct Characters medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1425

Problem TLDR

Smallest uniq-chars subsequence

Intuition

Didn’t solve. Stack-based algorightm was a little bit unexpected for me.

  // 46 minute TLE, n^3 algo, full search dp
    // 26^26 = 6*10^36
    // basically i give up at 1:28
    // the solution is stack-based
    // remove from stack if we find a better variant and stack peek
    // can be found forward

Greedily take every char. If current is better than the last taken, consider popping the last if there is the same in the suffix.

Approach

• hashset is not necessary, the result is less than 26

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

    fun smallestSubsequence(s: String) = buildString {
        val lastPos = IntArray(26); for (i in s.indices) lastPos[s[i]-'a'] = i
        for (i in s.indices) if (s[i] !in this) {
            while (length > 0 && last() > s[i] && lastPos[last()-'a'] > i)
                setLength(lastIndex)
            append(s[i])
        }
    }

    pub fn smallest_subsequence(s: String) -> String {
        let (mut last, mut res) = ([0; 128], String::new());
        for (i, b) in s.bytes().enumerate() { last[b as usize] = i; }
        for (i, b) in s.bytes().enumerate() { if !res.contains(b as char) {
            while res.bytes().last().map_or(false, |l| l > b && last[l as usize] > i) {
                res.pop();
            }
            res.push(b as char);
        }} res
    }