Shortest and Lexicographically Smallest Beautiful String

Shortest and Lexicographically Smallest Beautiful String

What is this problem about?

The Shortest and Lexicographically Smallest Beautiful String interview question gives you a binary string s and an integer k. A "beautiful" substring has exactly k ones. Among all beautiful substrings of s, find the one that is shortest. If multiple substrings have the same minimum length, return the lexicographically smallest one. This is a sliding window problem with a lexicographic comparison tiebreak.

Why is this asked in interviews?

Yelp, Wells Fargo, and IBM ask this problem because it combines sliding window (to find all substrings with exactly k ones) with length minimization and lexicographic comparison. It tests whether candidates can efficiently enumerate variable-size windows, track the minimum length, and handle the tiebreak — all in a single clean pass. The problem models substring search in binary data streams with quality constraints.

Algorithmic pattern used

The pattern is sliding window with minimum tracking. Use two pointers left and right. Expand right to include more characters. When the window contains exactly k ones, try to shrink from the left while maintaining at least k ones (i.e., shrink while s[left] == '0'). At each valid window, compare the length to the current best — update if shorter, or if same length and lexicographically smaller. Track the best (start, length) pair across all valid windows.

Example explanation

s = "100011", k = 2.

Find all substrings with exactly 2 ones:

• [0,4] = "10001" (length 5): ones=2, trim leading zeros: start=0 (s[0]='1', can't trim). Valid.
• [1,4] = "0001" doesn't work (only 1 one after trimming? check: ones=1).
• [2,5] = "0011" (ones=2, can trim zeros from left): trim → "11" start at index 4. Length 2.
• Shorter window [4,5] = "11" (ones=2). Length 2. Lexicographically smallest of length 2 with exactly 2 ones: "11".

Result: "11".

Common mistakes candidates make

• Not shrinking the left pointer past leading zeros — the shortest window of exactly k ones should start with a '1'.
• Comparing substring contents directly for each window — this is O(n × L) per comparison; use index tracking instead.
• Missing windows where k=0 — handle as a special case (shortest beautiful string is the empty string or a single '0').
• Not correctly resetting the window when the ones count drops below k.

Interview preparation tip

For the Shortest and Lexicographically Smallest Beautiful String coding problem, the sliding window string interview pattern is the approach. The critical optimization: after finding a valid window, shrink from the left while s[left] == '0' to get the minimum-length window starting with exactly k ones. IBM and Yelp interviewers appreciate when you handle the tiebreak by comparing the start indices and lengths rather than materializing substrings. Practice the "shrink from left while valid" variant of sliding window — it differs subtly from the standard "shrink until invalid" form.