LeetCode Entry

2904. Shortest and Lexicographically Smallest Beautiful String

26.08.2026 medium 2026 kotlin rust

Smallest substring with k-ones

2904. Shortest and Lexicographically Smallest Beautiful String medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1463

Problem TLDR

Smallest substring with k-ones

Intuition

Two pointers: always move the right, move the left while it is safe to shrink. Problem size is small, brute force is accepted.

Approach

• first take smallest length, then compare lexicographically

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(1)\)

Code

    fun shortestBeautifulSubstring(s: String, k: Int) =
    (k..s.length).firstNotNullOfOrNull { len ->
        s.windowed(len).filter { w -> w.count {it>'0'} == k }.minOrNull()
    } ?: ""

    pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
        (k as usize..=s.len()).find_map(|l| (0..=s.len() - l)
            .map(|i| &s[i..i + l])
            .filter(|w| w.matches('1').count() == k as usize)
            .min()
        ).unwrap_or("").into()
    }