Lexicographically smallest string after applying operations

String Depth-First Search Breadth-First Search Enumeration

79.4% acceptance

Feb 25, 2026

689

320

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b. You can apply either of the following two operations any number of times and in any order on s: Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. Rotate s to the right by b positions. Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashSet, VecDeque};

impl Solution {
  pub fn find_lex_smallest_string(s: String, a: i32, b: i32) -> String {
    let mut visited: HashSet<String> = HashSet::new();
    let mut queue: VecDeque<String> = VecDeque::new();
    let mut ans = s.clone();
    queue.push_back(s.clone());
    visited.insert(s);

    while let Some(cur) = queue.pop_front() {
      if cur < ans { ans = cur.clone(); }

      // Operation 1: add a to all odd indices
      let mut next1: Vec<u8> = cur.bytes().collect();
      for i in (1..next1.len()).step_by(2) {
        next1[i] = b'0' + (next1[i] - b'0' + a as u8) % 10;
      }
      let next1 = String::from_utf8(next1).unwrap();
      if !visited.contains(&next1) {
        visited.insert(next1.clone());
        queue.push_back(next1);
      }

      // Operation 2: rotate right by b
      let n = cur.len();
      let b = b as usize % n;
      let next2 = format!("{}{}", &cur[n-b..], &cur[..n-b]);
      if !visited.contains(&next2) {
        visited.insert(next2.clone());
        queue.push_back(next2);
      }
    }
    ans
  }
}