Remove duplicate letters

String Stack Greedy Monotonic Stack

52.8% acceptance

Jan 12, 2026

9273

700

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn remove_duplicate_letters(s: String) -> String {
    let mut last_occurrence = std::collections::HashMap::new();
    for (i, ch) in s.chars().enumerate() {
      last_occurrence.insert(ch, i);
    }
    
    let mut stack = Vec::new();
    let mut in_stack = std::collections::HashSet::new();
    
    for (i, ch) in s.chars().enumerate() {
      if in_stack.contains(&ch) {
        continue;
      }
      
      while !stack.is_empty() && *stack.last().unwrap() > ch && last_occurrence[stack.last().unwrap()] > i {
        let removed = stack.pop().unwrap();
        in_stack.remove(&removed);
      }
      
      stack.push(ch);
      in_stack.insert(ch);
    }
    
    stack.into_iter().collect()
  }
}