Move from brute-force thinking to an efficient approach using sliding window strategy.
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.
"abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.Example 1:
Input: s = "100011001", k = 3 Output: "11001" Explanation: There are 7 beautiful substrings in this example: 1. The substring "100011001". 2. The substring "100011001". 3. The substring "100011001". 4. The substring "100011001". 5. The substring "100011001". 6. The substring "100011001". 7. The substring "100011001". The length of the shortest beautiful substring is 5. The lexicographically smallest beautiful substring with length 5 is the substring "11001".
Example 2:
Input: s = "1011", k = 2 Output: "11" Explanation: There are 3 beautiful substrings in this example: 1. The substring "1011". 2. The substring "1011". 3. The substring "1011". The length of the shortest beautiful substring is 2. The lexicographically smallest beautiful substring with length 2 is the substring "11".
Example 3:
Input: s = "000", k = 1 Output: "" Explanation: There are no beautiful substrings in this example.
Constraints:
1 <= s.length <= 1001 <= k <= s.lengthProblem summary: 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. For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Sliding Window
"100011001" 3
"1011" 2
"000" 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2904: Shortest and Lexicographically Smallest Beautiful String
class Solution {
public String shortestBeautifulSubstring(String s, int k) {
int n = s.length();
String ans = "";
for (int i = 0; i < n; ++i) {
for (int j = i + k; j <= n; ++j) {
String t = s.substring(i, j);
int cnt = 0;
for (char c : t.toCharArray()) {
cnt += c - '0';
}
if (cnt == k
&& ("".equals(ans) || j - i < ans.length()
|| (j - i == ans.length() && t.compareTo(ans) < 0))) {
ans = t;
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #2904: Shortest and Lexicographically Smallest Beautiful String
func shortestBeautifulSubstring(s string, k int) (ans string) {
n := len(s)
for i := 0; i < n; i++ {
for j := i + k; j <= n; j++ {
t := s[i:j]
cnt := 0
for _, c := range t {
if c == '1' {
cnt++
}
}
if cnt == k && (ans == "" || j-i < len(ans) || (j-i == len(ans) && t < ans)) {
ans = t
}
}
}
return
}
# Accepted solution for LeetCode #2904: Shortest and Lexicographically Smallest Beautiful String
class Solution:
def shortestBeautifulSubstring(self, s: str, k: int) -> str:
n = len(s)
ans = ""
for i in range(n):
for j in range(i + k, n + 1):
t = s[i:j]
if t.count("1") == k and (
not ans or j - i < len(ans) or (j - i == len(ans) and t < ans)
):
ans = t
return ans
// Accepted solution for LeetCode #2904: Shortest and Lexicographically Smallest Beautiful String
impl Solution {
pub fn shortest_beautiful_substring(s: String, k: i32) -> String {
let n = s.len();
let mut ans = String::new();
for i in 0..n {
for j in i + (k as usize)..=n {
let t = &s[i..j];
if (t.matches('1').count() as i32) == k
&& (ans.is_empty() || j - i < ans.len() || (j - i == ans.len() && t < &ans))
{
ans = t.to_string();
}
}
}
ans
}
}
// Accepted solution for LeetCode #2904: Shortest and Lexicographically Smallest Beautiful String
function shortestBeautifulSubstring(s: string, k: number): string {
const n = s.length;
let ans: string = '';
for (let i = 0; i < n; ++i) {
for (let j = i + k; j <= n; ++j) {
const t = s.slice(i, j);
const cnt = t.split('').filter(c => c === '1').length;
if (
cnt === k &&
(ans === '' || j - i < ans.length || (j - i === ans.length && t < ans))
) {
ans = t;
}
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.
The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).
Review these before coding to avoid predictable interview regressions.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.