Lexicographically smallest string after substring operation

String Greedy

34.5% acceptance

Feb 25, 2026

279

194

Given a string s consisting of lowercase English letters. Perform the following operation: Select any non-empty substring then replace every letter of the substring with the preceding letter of the English alphabet. For example, 'b' is converted to 'a', and 'a' is converted to 'z'. Return the lexicographically smallest string after performing the operation.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_string(s: String) -> String {
    let mut s = s.into_bytes();
    let n = s.len();
    let mut i = 0;
    // Skip leading 'a's
    while i < n && s[i] == b'a' { i += 1; }
    if i == n {
      // All 'a's: shift last char to 'z'
      s[n - 1] = b'z';
    } else {
      // Shift non-'a' run starting at i
      while i < n && s[i] != b'a' {
        s[i] -= 1;
        i += 1;
      }
    }
    String::from_utf8(s).unwrap()
  }
}