Lexicographically smallest string after deleting duplicate characters

Hash Table String Stack Greedy Monotonic Stack

19.5% acceptance

Mar 16, 2026

You are given a string s that consists of lowercase English letters. You can perform the following operation any number of times (possibly zero times): Choose any letter that appears at least twice in the current string s and delete any one occurrence. Return the lexicographically smallest resulting string that can be formed this way.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn lex_smallest_after_deletion(s: String) -> String {
    // Find the lex smallest subsequence of s where each character that appears
    // in s keeps at least 1 copy and at most freq[c] copies.
    //
    // Two-phase approach:
    // Phase 1: Greedy monotone stack to reorder/remove larger chars before smaller ones.
    // Phase 2: Remove from the end any character that still has duplicates (since
    //          a shorter prefix is always lex smaller).

    let bytes = s.as_bytes();
    let n = bytes.len();

    let mut remaining = vec![0u32; 26];
    for &b in bytes {
      remaining[(b - b'a') as usize] += 1;
    }

    let mut stack: Vec<u8> = Vec::new();
    let mut in_stack = vec![0u32; 26];

    for i in 0..n {
      let c = bytes[i];
      let ci = (c - b'a') as usize;

      // Try to pop larger characters from stack top
      while let Some(&top) = stack.last() {
        if top > c {
          let ti = (top - b'a') as usize;
          // Can pop if at least 1 copy of top remains elsewhere
          if in_stack[ti] - 1 + remaining[ti] >= 1 {
            stack.pop();
            in_stack[ti] -= 1;
          } else {
            break;
          }
        } else {
          break;
        }
      }

      stack.push(c);
      in_stack[ci] += 1;
      remaining[ci] -= 1;
    }

    // Phase 2: Remove from the end while the last char has duplicates in the result.
    // A shorter string that is a prefix is always lex smaller.
    while stack.len() > 0 {
      let top = *stack.last().unwrap();
      let ti = (top - b'a') as usize;
      if in_stack[ti] >= 2 {
        stack.pop();
        in_stack[ti] -= 1;
      } else {
        break;
      }
    }

    String::from_utf8(stack).unwrap()
  }
}