Using a robot to print the lexicographically smallest string

Hash Table String Stack Greedy

62.5% acceptance

Feb 25, 2026

1153

308

You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty: * Remove the first character of a string s and give it to the robot. The robot will append this character to the string t. * Remove the last character of a string t and give it to the robot. The robot w ill write this character on paper. * Return the lexicographically smallest string that can be written on the paper . *

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn robot_with_string(s: String) -> String {
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    // suffix_min[i] = minimum character in s[i..]
    let mut suffix_min = vec![b'z' + 1; n + 1];
    for i in (0..n).rev() {
      suffix_min[i] = suffix_min[i + 1].min(s[i]);
    }
    let mut stack: Vec<u8> = Vec::new();
    let mut result: Vec<u8> = Vec::new();
    for i in 0..n {
      stack.push(s[i]);
      while !stack.is_empty() && *stack.last().unwrap() <= suffix_min[i + 1] {
        result.push(stack.pop().unwrap());
      }
    }
    while let Some(c) = stack.pop() {
      result.push(c);
    }
    String::from_utf8(result).unwrap()
  }
}