Smallest subsequence of distinct characters

String Stack Greedy Monotonic Stack

63.1% acceptance

Feb 25, 2026

2753

200

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_subsequence(s: String) -> String {
    let mut last = [0usize; 26];
    for (i, b) in s.bytes().enumerate() { last[(b - b'a') as usize] = i; }
    let mut stack: Vec<u8> = vec![];
    let mut in_stack = [false; 26];
    for (i, b) in s.bytes().enumerate() {
      let c = (b - b'a') as usize;
      if in_stack[c] { continue; }
      while let Some(&top) = stack.last() {
        let t = (top - b'a') as usize;
        if top > b && last[t] > i {
          stack.pop();
          in_stack[t] = false;
        } else { break; }
      }
      stack.push(b);
      in_stack[c] = true;
    }
    String::from_utf8(stack).unwrap()
  }
}