Check if string is transformable with substring sort operations

String Greedy Sorting

51.1% acceptance

Feb 25, 2026

456

Given two strings s and t, transform string s into string t using the following operation any number of times: Choose a non-empty substring in s and sort it in place so the characters are in ascending order. Return true if it is possible to transform s into t. Otherwise, return false.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_transformable(s: String, t: String) -> bool {
    // For each digit d (0-9), maintain a queue of positions where d appears in s
    // Process t from left to right: for each t[i]=d, find leftmost occurrence of d in s
    // Ensure no digit smaller than d sits between that position and the front
    use std::collections::VecDeque;
    let s: Vec<usize> = s.bytes().map(|b| (b - b'0') as usize).collect();
    let t: Vec<usize> = t.bytes().map(|b| (b - b'0') as usize).collect();
    let mut pos: Vec<VecDeque<usize>> = vec![VecDeque::new(); 10];
    for (i, &d) in s.iter().enumerate() {
      pos[d].push_back(i);
    }
    for &d in &t {
      if pos[d].is_empty() {
        return false;
      }
      let idx = *pos[d].front().unwrap();
      // Check that no digit smaller than d has an index < idx
      for smaller in 0..d {
        if let Some(&front) = pos[smaller].front() {
          if front < idx {
            return false;
          }
        }
      }
      pos[d].pop_front();
    }
    true
  }
}