Shortest and Lexicographically Smallest Beautiful String - Video Solutions

Problem Overview: Given a binary string s and an integer k, you must find the shortest substring containing exactly k occurrences of '1'. If multiple substrings share the same minimal length, return the lexicographically smallest one. If no such substring exists, return an empty string.

Approach 1: Sliding Window Technique (O(n) time, O(1) space)

This approach uses the classic Sliding Window pattern. Maintain two pointers left and right and expand the window by moving right. Track how many '1' characters exist in the current window. When the count exceeds k, move left forward until the window becomes valid again. Every time the window contains exactly k ones, attempt to shrink it from the left while preserving the condition to ensure the substring is as short as possible.

Each valid window represents a candidate substring. Compare it with the current best result: prefer the shorter substring, and if lengths match, pick the lexicographically smaller one using standard string comparison. Since each character enters and leaves the window at most once, traversal is linear. Space usage remains O(1) because only counters and pointers are stored.

Approach 2: Prefix Sum and Two Pointers (O(n) time, O(n) space)

This method relies on prefix sums to quickly compute the number of '1' characters in any substring. Build a prefix array where prefix[i] stores the count of ones up to index i. With this structure, the number of ones in s[l..r] becomes prefix[r+1] - prefix[l]. Use a Two Pointers strategy to scan possible windows while checking the count using prefix lookups.

When a window contains exactly k ones, attempt to tighten the left boundary to minimize the substring length. Record candidate substrings and apply lexicographic comparison when lengths tie. Prefix sums make the count check constant time, avoiding repeated scans of the substring. This approach is helpful if you already rely on prefix arrays for multiple range queries in a larger system.

The core difficulty lies in balancing two goals: minimal length and lexicographical order. The sliding window approach naturally produces minimal windows while scanning left to right, which keeps comparisons manageable.

Recommended for interviews: The Sliding Window approach is the expected solution. It demonstrates strong understanding of window expansion, contraction, and maintaining constraints in linear time. Mentioning a prefix sum alternative shows deeper familiarity with string range-count techniques, but the sliding window version is typically cleaner and uses constant extra space.