Lexicographically smallest string after a swap

String Greedy

54.5% acceptance

Feb 25, 2026

100

Given a string s containing only digits, return the lexicographically smallest string that can be obtained after swapping adjacent digits in s with the same parity at most once. Digits have the same parity if both are odd or both are even.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn get_smallest_string(s: String) -> String {
    let mut bytes: Vec<u8> = s.into_bytes();
    let n = bytes.len();
    for i in 0..n - 1 {
      let a = bytes[i] - b'0';
      let b = bytes[i + 1] - b'0';
      // Same parity and s[i] > s[i+1]: swap to get lexicographically smaller
      if a % 2 == b % 2 && a > b {
        bytes.swap(i, i + 1);
        break;
      }
    }
    String::from_utf8(bytes).unwrap()
  }
}