Shortest and lexicographically smallest beautiful string

String Sliding Window

40.9% acceptance

Feb 25, 2026

204

You are given a binary string s and a positive integer k. A substring of s is beautiful if the number of 1's in it is exactly k. Let len be the length of the shortest beautiful substring. Return the lexicographically smallest beautiful substring of string s with length equal to len. If s doesn't contain a beautiful substring, return an empty string. A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
    let k = k as usize;
    let n = s.len();
    let bytes = s.as_bytes();
    let mut best = String::new();
    let mut best_len = usize::MAX;

    for i in 0..n {
      let mut ones = 0usize;
      for j in i..n {
        if bytes[j] == b'1' { ones += 1; }
        if ones == k {
          let len = j - i + 1;
          let sub = &s[i..=j];
          if len < best_len || (len == best_len && sub < best.as_str()) {
            best_len = len;
            best = sub.to_string();
          }
          break;
        }
      }
    }
    best
  }
}