Construct smallest number from di string

String Backtracking Stack Greedy

85.6% acceptance

Feb 25, 2026

1659

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing. A 0-indexed string num of length n + 1 is created using the following conditions: num consists of the digits '1' to '9', where each digit is used at most once. If pattern[i] == 'I', then num[i] < num[i + 1]. If pattern[i] == 'D', then num[i] > num[i + 1]. Return the lexicographically smallest possible string num that meets the conditions.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_number(pattern: String) -> String {
    let n = pattern.len();
    let chars: Vec<char> = pattern.chars().collect();
    let mut res: Vec<i32> = vec![];
    let mut stack: Vec<i32> = vec![];
    for i in 0..=n {
      stack.push((i + 1) as i32);
      if i == n || chars[i] == 'I' {
        while let Some(x) = stack.pop() { res.push(x); }
      }
    }
    res.iter().map(|&d| char::from_digit(d as u32, 10).unwrap()).collect()
  }
}