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 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.
The sliding window technique involves maintaining a window over the string that adjusts to include exactly k '1's, which constitutes a beautiful substring. We then aim to find the shortest such window, and among those, the lexicographically smallest substring.
This C implementation uses a sliding window (two pointers, l and r) to find the shortest segment of the string that contains exactly k '1's. It also keeps track of the lexicographically smallest substring that fits these criteria by comparing each new candidate with the smallest found so far.
Time Complexity: O(n), where n is the length of the string. This is because each character is processed at most twice (once by r and once by l).
Space Complexity: O(k) for storing the result substring.
This approach uses a prefix sum to keep track of the number of '1's up to each index and then applies a two-pointer technique to identify the shortest valid substring. The idea is to efficiently calculate the number of '1's in any segment by referencing the prefix sum array. Once a substring with exactly k '1's is found, it is compared against the current smallest lexicographical segment stored.
This C solution uses the prefix sum array to keep track of the number of '1's up to each position. The two pointers help identify the substring range with exactly k '1's and update the result if it's the smallest found.
Time Complexity: O(n), for constructing prefix sum and traversing the string. Space Complexity: O(n) for the prefix sum array.
We can enumerate all substrings s[i: j], where i \lt j, and check if they are beautiful substrings. If so, we update the answer.
The time complexity is O(n^3), and the space complexity is O(n). Here, n is the length of the string s.
We can also use two pointers to maintain a sliding window, where pointer i points to the left boundary of the window, and pointer j points to the right boundary of the window. Initially, i and j both point to 0. In addition, we use a variable cnt to record the number of 1s in the sliding window.
We first move pointer j to the right, add s[j] to the sliding window, and update cnt. If cnt is greater than k, or if i is less than j and s[i] is 0, we move pointer i to the right and update cnt.
When cnt equals k, we have found a beautiful substring. We compare it with the current answer and update the answer if necessary.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the string s.
| Approach | Complexity |
|---|---|
| Sliding Window Technique | Time Complexity: O(n), where n is the length of the string. This is because each character is processed at most twice (once by |
| Prefix Sum and Two Pointers | Time Complexity: O(n), for constructing prefix sum and traversing the string. Space Complexity: O(n) for the prefix sum array. |
| Enumeration | — |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Technique | O(n) | O(1) | Best general solution for scanning substrings with constraints like exactly k ones |
| Prefix Sum + Two Pointers | O(n) | O(n) | Useful when prefix arrays are already needed for multiple substring queries |
2904. Shortest and Lexicographically Smallest Beautiful String 🔥 || Brute-Optimal (Sliding Window) 🔥 • Ayush Rao • 1,394 views views
Watch 8 more video solutions →Practice Shortest and Lexicographically Smallest Beautiful String with our built-in code editor and test cases.
Practice on FleetCode