Lexicographically minimum string after removing stars

Hash Table String Stack Greedy Heap (Priority Queue)

51.0% acceptance

Feb 24, 2026

589

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters. While there is a '*', do the following operation: Delete the leftmost '*' and the smallest non-'*' character to its left (rightmost if multiple). Return the lexicographically smallest resulting string after removing all '*' characters.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn clear_stars(s: String) -> String {
    let bytes = s.as_bytes();
    let n = bytes.len();
    // stacks[c] stores indices of character 'a'+c seen so far (not deleted)
    let mut stacks: [Vec<usize>; 26] = std::array::from_fn(|_| Vec::new());
    let mut deleted = vec![false; n];

    for (i, &b) in bytes.iter().enumerate() {
      if b == b'*' {
        deleted[i] = true;
        // Delete the rightmost occurrence of the smallest char to the left
        for c in 0..26 {
          if !stacks[c].is_empty() {
            let j = stacks[c].pop().unwrap();
            deleted[j] = true;
            break;
          }
        }
      } else {
        stacks[(b - b'a') as usize].push(i);
      }
    }

    bytes
      .iter()
      .enumerate()
      .filter(|&(i, _)| !deleted[i])
      .map(|(_, &b)| b as char)
      .collect()
  }
}