Lexicographically smallest string after operations with constraint

String Greedy

62.9% acceptance

Feb 23, 2026

165

You are given a string s and an integer k. Define a function distance(s1, s2) between two strings s1 and s2 of the same length n as: The sum of the minimum distance between s1[i] and s2[i] when the characters from 'a' to 'z' are placed in a cyclic order, for all i in the range [0, n - 1]. For example, distance("ab", "cd") == 4, and distance("a", "z") == 1. You can change any letter of s to any other lowercase English letter, any number of times. Return a string denoting the lexicographically smallest string t you can get after some changes, such that distance(s, t) <= k.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn get_smallest_string(s: String, k: i32) -> String {
    let mut k = k;
    let mut result = s.into_bytes();
    for b in result.iter_mut() {
      let c = *b - b'a';
      // Cyclic distance to 'a'
      let dist_to_a = c.min(26 - c) as i32;
      if dist_to_a <= k {
        k -= dist_to_a;
        *b = b'a';
      } else {
        // Move as close to 'a' as possible: go backward k steps
        *b -= k as u8;
        break;
      }
    }
    String::from_utf8(result).unwrap()
  }
}