Lexicographically smallest beautiful string

String Greedy

38.1% acceptance

Feb 25, 2026

224

A string is beautiful if: It consists of the first k letters of the English lowercase alphabet. It does not contain any substring of length 2 or more which is a palindrome. You are given a beautiful string s of length n and a positive integer k. Return the lexicographically smallest string of length n, which is larger than s and is beautiful. If there is no such string, return an empty string.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_beautiful_string(s: String, k: i32) -> String {
    let k = k as u8;
    let mut chars: Vec<u8> = s.bytes().map(|b| b - b'a').collect();
    let n = chars.len();
    
    fn valid_from(chars: &[u8], i: usize, from: u8, k: u8) -> Option<u8> {
      for c in from..k {
        if i >= 1 && chars[i-1] == c { continue; }
        if i >= 2 && chars[i-2] == c { continue; }
        return Some(c);
      }
      None
    }
    
    // Try to increment from position n-1 backward
    let mut pos = n as i64 - 1;
    while pos >= 0 {
      let i = pos as usize;
      let start = chars[i] + 1;
      if let Some(c) = valid_from(&chars, i, start, k) {
        chars[i] = c;
        // Fill positions after i with smallest valid chars
        for j in (i+1)..n {
          chars[j] = valid_from(&chars, j, 0, k).unwrap();
        }
        return chars.iter().map(|&c| (b'a' + c) as char).collect();
      }
      pos -= 1;
    }
    String::new()
  }
}